基于格的分层无证书代理签名方案

农 强，张棒棒，欧阳玉豪

（1.闽南师范大学 计算机学院，福建 漳州 363000；2.数据科学与智能应用福建省高等学校重点实验室（闽南师范大学），福建 漳州 363000）

0 引言

代理签名是一种特殊的数字签名，广泛应用于需要签名权力委托的应用场合。近年来，为解决基于身份密码系统中固有的密钥托管问题，一些无证书代理签名［1-5］被相继提出，然而这些代理签名的安全性主要基于椭圆曲线上的离散对数或者双线性对困难问题假设。随着量子计算机技术的不断突破，传统方案的安全性将受到威胁，而基于格的密码体制被普遍认为是抗量子攻击的。Gentry 等［6］利用原像采样构造了一类单向陷门函数，并提出在随机预言机模型下可证安全的数字签名方案，随后格密码体制进入快速发展阶段。然而原像采样需要在拥有陷门的情况下获取原像，导致签名方案的计算复杂度较高。Lyubashevsky［7］在2012 年欧洲密码年会上摒弃原像采样函数，提出拒绝采样的概念，它构造的无陷门格签名所采用的密钥是一个小范数矩阵，而不是陷门基，遵循Fiat-Shamir 模式，显著地提高了签名效率。Ducas等［8］在Lyubashevsky 工作的基础上提出双峰高斯分布以减小标准差的方式提高了效率，却被证明存在侧信道攻击［9］，缺乏安全性。

其次，已有的无证书代理签名方案在大规模分布式异构网络环境中往往会面临单点失效问题。Horwitz 等［10］首次提出了基于身份的分层签名方案，一定程度上解决了单点失效问题并支持负载均衡；Zhang 等［11］首次提出基于无证书的分层签名方案，该方案不存在密钥托管问题且签名尺寸与层次结构的深度无关。在现实世界中，代理签名已被广泛应用于电子商务、分布式系统、物联网和无线自组网等场景，如Verma 等［12］将代理签名技术应用于医疗无线传感器网络，以对远程无线体域网用户进行基于电子医疗监测的大数据采集，在传输、存储和计算开销方面都取得了较好的效果；He等［13］将代理签名技术应用于无人机网络，显著减少了地面控制中心与无人机之间的传播时延，从而提高了无人机的工作效率。这些应用系统具有网络规模大、节点数量多及地理分布广泛等特点。为了解决单一密钥生成中心（Key Generation Center，KGC）的瓶颈问题，可通过在代理签名方案中引入分层机制，由根KGC 按照层次结构的顺序将密钥管理任务及用户认证权限分散到其子域KGC，以实现高效的密钥管理和负载均衡。然而，在已提出的分层结构中，根KGC 把密钥分发及用户认证的权限委托给其子域KGC，子域KGC 进而向下迭代，用户作为最底层的叶子节点，其密钥仅由其父节点即最底层的KGC 来分发，这就造成了系统资源的极大浪费。如同在操作系统的多级目录结构中，只有最底层的目录才具有存储普通文件的权限，而其上层目录仅能存储目录文件，显然是不合理的。

针对上述问题，在Lyubashevsky［7］提出的拒绝采样技术和无陷门格签名的基础上，本文构造了一类基于格的分层无证书代理签名方案。该方案是首个允许签名人来自不同层级隶属于不同KGC 的代理签名方案，优点是将密钥分发及用户认证功能分布到更多的KGC，能够实现更好的负载均衡且更具灵活性。所提方案在随机预言机模型下基于格上标准的小整数解（Short Integer Solution，SIS）困难问题假设是可证安全的。与已有的基于格的代理签名方案比较，所提方案具有较低的通信延迟和计算开销。相较于传统的无证书代理签名方案，所提方案在计算开销方面具备优势。

1 基础知识

1.1 符号说明

令R 表示实数集，Z 表示整数集。用粗体大写字母表示矩阵，如A；粗体小写字母表示向量，如a。AT表示矩阵A的转置，‖a‖表示向量a的欧几里得范数。令OS（Original Signer）表示原始签名人，PS（Proxy Signer）表示代理签名人。OSj表示第j层原始签名人，PSi表示第i层代理签名人，表示第j层原始签名人的身份信息表示第i层代理签名人的身份信息。

1.2 格的定义

1.3 拒绝采样

根据文献［7］的定义，设V∈Zm，σ∈R 且V中所有元素的范数都小于T，满足σ=，且h：V→R 是一个概率分布。那么存在一个常数E=O(1)满足算法alg-A 的分布和算法alg-B 的分布之间的统计距离为2-w(logm)/E，且算法alg-A 有输出的概率至少为(1-2-w(logm))/E。

1.4 困难问题

SISq，m，β问题：给定素数q，矩阵和实数β，找到一个非零向量e∈Zm使得Ae≡0 mo dq且‖e‖≤β。

2 安全模型

Boldyreva 等［14］首次给出了代理签名的安全定义，并建立了形式化的安全模型。在该模型中，代理签名的安全性要求在适应性选择授权文件和消息攻击下，任意一个OS 或PS 均无法伪造一个有效授权，也无法伪造一个有效代理签名。结合Al-Riyami 等［15］所定义的无证书签名体制下两类敌手，即用户攻击和KGC 攻击，分别考虑OS 和PS 的安全性，把分层无证书代理签名的敌手定义为Ai（i∈[1，4]），具体分类如下：

1）A1：敌手不知道PS 的完整密钥但可以替换任意用户的公钥，其试图伪造一个有效代理签名。

2）A2：敌手不知道OS 的完整密钥但可以替换任意用户的公钥，其试图伪造一个有效授权。

3）A3：敌手不知道PS 的完整密钥但拥有系统主密钥，其试图伪造一个有效代理签名。

4）A4：敌手不知道OS 的完整密钥但拥有系统主密钥，其试图伪造一个有效授权。

综上所述，分层无证书代理签名的不可伪造性通过敌手Ai和挑战者C之间模拟的4 个游戏来定义，游戏采用与文献［1-5］类似的随机预言机模型。Ai在每个游戏中经过自适应询问后，最终输出授权文件ω*上的有效授权cert*或消息μ*上的有效代理签名Sig*。如果满足以下条件，认为Ai赢得了游戏。

3 分层无证书代理签名方案

本章以Lyubashevsky［7］的工作为基础，构建了一种格上的分层无证书代理签名方案，所提方案既不使用原像采样技术也不使用陷门技术，由如下算法构成：

4 安全分析

定理1在随机预言机模型下，若存在多项式时间敌手A1能够以不可忽略的概率成功伪造代理签名，那么存在一个挑战者C也能够以不可忽略的概率解决SIS 困难问题。

证明 在SIS 困难问题假设下，利用A1和挑战者C之间的游戏来证明在没有PS 完整密钥的情况下代理签名是不可伪造的，过程如下：

定理3在随机预言机模型下，若存在多项式时间敌手A3能够以不可忽略的概率成功伪造代理签名，那么存在一个挑战者C也能够以不可忽略概率解决SIS 困难问题。

证明 在SIS 困难问题假设下，利用A3和挑战者C之间的游戏来证明在没有PS 完整密钥的情况下代理签名是不可伪造。过程如下：

定理4在随机预言机模型下，若存在多项式时间敌手A4能够以不可忽略的概率成功伪造授权，那么存在一个挑战者C也能够以不可忽略的概率解决SIS 困难问题。

证明 在SIS 困难问题假设下，利用A4和挑战者C之间的游戏来证明在没有OS 完整密钥的情况下无法伪造代理授权。

C模拟的询问预言机与定理3 类似，区别在于A4无需询问H4，H5和签名预言机。当A4结束询问阶段后，输出身份和授权文件上有效的伪造代理授权。由定理2 的证明过程很容易证明其签名不可伪造，这里不再赘述。

5 性能评价

将所提方案与传统的较为高效的无双线性对的无证书代理签名方案［3］和现有基于格的代理签名方案［17-19］相比较。Shor［20］已经证明传统方案所依赖的经典数论难题，如RSA 问题和离散对数问题，都可以用量子计算机以多项式时间求解，即使取任意长度的密钥。而格中的很多难题，如SIS，已被证明是NP 困难的，因此基于格的密码体制被普遍认为是抗量子攻击的。

实验采用的硬件环境为Intel Core i7-8550u CPU 和DDR3 8 GB RAM，操作系统为Windows 10，使用JAVA JDK 9.0.4 在IDEA 2020 上通过JBLAS 矩阵运算库和JPBC 2.0.0密码库模拟相关的密码运算。为了保证方案在实施过程中的安全性，对于所提方案和现有基于格的代理签名方案，参考文献［7］的系统参数设置，取n=512，q=227，d=1，k=80，m=64+nlogq/log(2d+1) ≈8 786，κ=28 和σ=≈31 945，每种运算运行一百万次取其耗时均值，得出矩阵向量乘法耗时TM≈0.514 ms，向量模加法耗时TA≈0.024 ms。对于传统方案，在不失一般性的前提下，设G是一个阶为q的循环加法群，生成元P∈G为非奇异椭圆曲线y2=x3+ax+bmodp上的点，其中a，b∈，p和q为160 比特素数，得出标量乘耗时Tm≈4.749 ms，标量加耗时Ta≈0.019 ms。

表1 比较了各方案的签名和验证开销。从表1 可以看出，所提方案的代理签名和验证开销与层级无关，验证效率要优于其他方案。

表1 签名和验证开销比较 单位：msTab.1 Signature and verification overhead comparison unit：ms

表2 给出了所提方案的层级对通信开销的影响。由于层级l通常是一个小整数，从表2 可以看出，所提方案的代理公钥尺寸是一个常数，与层级无关，授权证书、代理密钥和签名尺寸也非层级的线性量。

表2 层级对通信开销的影响 单位：bitTab.2 Impact of hierarchy on communication overhead unit：bit

表3 比较了各方案的代理密钥和签名尺寸。由于所比较的方案均为无分层结构，表3 中只给出所提方案的参数i和j取值均为1 的情形。文献［17］方案中的参数l′为哈希函数的输出长度，取l′=80。文献［18］方案中的参数λ′为系统安全参数，取λ′=512。从表3 可以看出，与其他基于格的代理签名方案相比较，所提方案的代理密钥和签名尺寸较小，而传统的基于离散对数问题的无证书代理签名方案在存储和通信开销上更具优势。

表3 代理密钥和签名尺寸比较 单位：bitTab.3 Proxy key and signature size comparison unit：bit

6 结语

随着量子计算机技术的不断成熟，已有基于经典数论难题的无证书代理签名将不再安全，设计后量子时代安全的替代方案已迫在眉睫。基于SIS 难题假设，结合拒绝采样技术和无陷门格签名，本文构造一种分层无证书代理签名方案，其密码操作时间复杂度与层次的深度无关。该方案首次实现了不同层级隶属不同KGC 的两个用户之间的代理签名权限委托，非常适合大规模用户的使用，对提高已有层次密码系统的均衡负载能力也具有指导意义。本文方案的性能明显优于已有的基于格的代理签名方案，相较于传统方案，其计算开销较小，而密钥和签名尺寸较大，这也是当前格密码体制的固有弊端。为进一步提升方案的空间效率，下一步的研究将逐步关注能结合传统椭圆曲线密码与格密码的混合公钥密码算法，构造更为高效的分层无证书代理签名方案。