1996年，Mambo、Usuda和Okamoto^[1]提出了代理签名的概念.在代理签名方案中，原始签名者把他的签名权利委托给代理签名者，由代理签名者代替他来完成签名.在方案中验证者可以区分签名是代理签名还是原始签名.鉴于代理签名的这种性质，研究者把它应用到匿名投票、移动代理、网格计算、电子现金中.而目前利用量子算法可以在多项式时间内解决大整数分解和离散对数问题，那么基于这两种假设的方案在量子环境下将被攻破.因此，构造量子环境下安全的代理签名方案是非常有意义的.格公钥密码作为近年来发展最快、受关注程度最高的后量子密码之一，具有良好的密码学性质.目前，很多学者对基于格的代理签名进行了研究，取得了一些成果^[2-5].笔者利用无陷门签名技术和小范数向量传递技术构造了一个基于格的代理签名方案，降低了代理签名私钥和代理签名的尺寸.

设是一个m×m阶矩阵，并且b₁, …, b_m∈R^m是线性无关的向量.一个m维满秩格Λ定义为向量b₁, …, b_m的所有整系数线性组合所构成的集合，即

这里b₁, …, b_m构成了格Λ的一组基.

定义1  小整数解问题(SIS_{q, m, β}，small integer solution problem)：给定一个随机的矩阵A∈Z_q^n×m和一个实数β，找到一个非零向量e，使得Ae=0mod q且‖e‖≤β，‖·‖表示欧几里得范数.

引理1^[6]  对于任意的矩阵A∈Z_q^n×m，m＞64+nlog q/log (2d+1)，对随机选择的s∈{-d, …, 0, …, d}^m，以1-2^-100的概率存在另一个s′∈{-d, …, 0, …, d}^m使得As=As′.

对于任意c＞0，实数σ＞0，一个m维格Λ，定义格Λ上的离散高斯分布为

当c=0时，简写为D_{Λ, σ}.整数Z构成的格的高斯分布简写为D_{σ, c}.

引理2^[7]  设q≥2，矩阵A∈Z_q^n×m，m＞n.设T是格Λ_q^⊥(A)的一组基，.那么对于c∈R^m，u∈Z_qⁿ，有

negl(n)表示关于n的一个可忽略的量.

该方案使用了3个Hash函数：

H₁:{0, 1}^*→D_H1={c:c∈{-1, 0, 1}^k, ‖c‖₁≤κ₁}

H₂:{0, 1}^*→D_H2={c:c∈{-1, 0, 1}^l, ‖c‖₁≤κ₂}

H₃:id→{-1, 0, 1}^k×l，H₁, H₂被看做随机预言机，l＜k＜m，κ_i满足, i=1, 2.

1) 密钥生成：随机选择矩阵A∈Z_q^n×m，S，S₁∈{-d, …, 0, …, d}^m×k，计算T=ASmod q，T₁=AS₁mod q.原始签名者的公、私钥对为(A, T, S)，代理者自己的公、私钥对为(A, T₁, S₁).

2) 代理签名密钥生成：对于代理签名者id，计算U_id=H₃(id)∈{-1, 0, 1}^k×l，S₂=SU_id∈Z^m×l，T₂=TU_idmod q，代理签名密钥为S₂，对应的公钥为T₂.原始签名者通过安全信道把代理签名密钥S₂发送给代理者.

3) 代理者验证：代理者收到代理签名密钥后，检查AS₂=TU_idmod q是否成立，若成立，则接受代理签名密钥，否则拒绝.

4) 代理签名：输入一个消息μ，代理者自己的私钥S₁，代理签名密钥S₂，签名如下：

① 选择两个向量y₁, y₂←D_σ^m；

② 计算c₁=H₁(Ay₁, μ)，c₂=H₂(Ay₂, μ)；

③ 计算z₁=S₁c₁+y₁∈Z_q^m，z₂=S₂c₂+y₂∈Z_q^m；

④ 以的概率输出(z₁, c₁)，以的概率输出(z₂, c₂)；

5) 验证：输入消息μ及其对应的签名(z₁, c₁)，(z₂, c₂)，矩阵A、T₁、T₂，验证，c_i=H_i(Az_i-T_ic_i, μ)，i=1, 2是否同时成立，若成立，则接受；否则，拒绝.

下面给出方案的正确性验证与安全性证明.在定理1中，详细给出代理签名的正确性验证.定理2的不可伪造性说明了任何人都不能伪造代理签名者的签名，保证了代理签名者的安全性.定理3证明了任何人都不能伪造原始签名者的签名或者委托代理签名的权利，保证了原始签名者的安全性.

定理1(正确性)

对于消息μ及其对应的代理签名(z₁, c₁)，(z₂, c₂)，需要验证，c_i=H_i(Az_i-T_ic_i, μ)，i=1, 2，同时成立.首先

其次  Az_i-T_ic_i=A(S_ic_i+y_i)-T_ic_i=Ay_i

因此c_i=H₁(Ay_i, μ)=H₁(Az_i-T_ic_i, μ)，i=1, 2.

定理2(不可伪造性)

假设存在一个概率多项式时间敌手能够以不可忽略的概率ε产生一个有效的伪造代理签名，那么就存在一个算法，对于一个随机矩阵A∈Z_q^n×m，能够以至少

的概率，找到一个非零向量v，使得，且Av=0.

证明  需要分两种情况来讨论代理签名的不可伪造性.其一，恶意的原始签名者(拥有代理签名密钥，但没有代理签名者的密钥)不能伪造代理签名；其二，恶意的第三方(没有代理签名密钥，也没有代理签名者的密钥)不能够伪造代理签名.由于恶意的第三方的攻击能力弱于恶意的原始签名者，所以只需讨论恶意的原始签名者的不可伪造性.设存在一个概率多项式时间敌手(恶意的原始签名者)，在进行了q_H2次随机预言机H₂询问和q_s次签名询问之后，可以以不可忽略的概率ε伪造一个有效的代理签名.由于敌手已经知道了代理签名密钥，那么它需要产生一个代理签名者本身签名的伪造，即产生一个伪造签名(μ, z, c).需要构造一个多项式时间算法，利用的优势来攻破小整数解问题SIS_{q, m, β}. 需要模拟随机预言机H₂和签名预言机，模拟如下.

1) 随机预言机H₂询问：维持一个列表(μ_j, z_j, c_j)，当敌手询问消息μ_j的随机预言机H₂值时，先检查列表中是否有μ_j，若有，则输出c_j；否则，从D_H2中随机选择一个c_j，并选择一个z_j←D_σ^m，令c_j=H₂(Az_j-Tc_j, μ_j). 存储(μ_j, z_j, c_j)，并返回c_j给作为对μ_j的随机预言机H₂询问.

2) 签名询问：当敌手询问消息μ_j的签名，假设对所有要进行签名询问的消息已经进行过随机预言机H₂询问. 从列表中取回(μ_j, z_j, c_j)，并返回(z_j, c_j)给敌手.

3) 伪造：当敌手决定结束这些询问之后，输出一个伪造(μ, z, c). 要利用这个伪造签名(μ, z, c)来解决小整数解问题.由于签名询问的消息已经在签名询问中询问过了，那么敌手至多进行t=q_s+q_H2次随机预言机H₂询问，随机选择c₁, …, c_t←D_H2.这个伪造的签名满足，且c=H₂(Az-Tc, μ).对于给定u=Az-Tc，敌手产生一个c使得c=H₂(u, μ)的概率为1/|D_H2|，因此c以1-1/|D_H2|的概率是消息μ在随机预言机H₂询问时得到的，即c∈{c₁, …, c_t}，那么敌手产生一个有效的伪造，并且c∈{c₁, …, c_t}的概率为ε-1/|D_H2|.不妨设c=c_j.这里c_j有两种可能，一种是c_j是在签名询问中产生的，另一种是在随机预言机H₂询问中产生的.

当c_j在签名询问中产生.由于c=c_j，则H₂(Az-Tc, μ)=H₂(Az_j-Tc, μ_j).如果μ≠μ_j或Az-Tc≠Az_j-Tc，则意味着敌手找到了c_j的一个原像.所以μ=μ_j，Az-Tc=Az_j-Tc，那么A(z-z_j)=0.又由于z-z_j≠0，且，那么有.

现在考虑c_j是在随机预言机H₂询问中产生的.在这种情况下，记录敌手对消息μ的伪造签名(z, c_j)，并产生新的随机的c′₁, …, c′_t←D_H2.那么由一般的分支引理可知，敌手产生一个关于消息μ的新的伪造签名(z′, c′_j)(c_j≠c′_j)的概率为，即敌手产生消息μ的伪造签名(z, c_j)和(z′, c′_j)的概率.由于Az-Tc_j=Az′-Tc′_j，把T=AS代入，得到A(z-z′+Sc′_j-Sc_j)=0，由于，，所以.

现在要说明z-z′+Sc′_j-Sc_j≠0.由引理1可知，以至少1-2^-100的概率存在另一个私钥S′使得AS=AS′，所以若z-z′_j+S(c′_j-c_j)=0，则z-z′_j+S′(c′_j-c_j)≠0.由于在整个模拟过程中并没有出现S，所以不知道使用的是哪一个，这就说明得到非零向量的概率至少为1/2.

定理3  代理签名者不能得到原始签名者的私钥，且任何人(包括代理签名者)在不拥有原始签名者私钥的情况下，都不能够伪造代理签名密钥.

证明  首先证明代理签名者不能得到原始签名者的私钥，只需要证明如果代理签名者能够得到原始签名者的私钥，那么就可以利用代理签名者的能力解决SIS_{q, m, β}问题，即对于一个随机矩阵A∈Z_q^n×m，找到一个非零向量v，使得‖v‖≤β，且Av=0.令敌手为恶意的代理签名者，假设敌手在进行了q_prk(lq_prk＜k)次代理签名密钥询问之后，可以以不可忽略的概率ε得到原始签名者的私钥.需要构造一个算法利用的优势来解决SIS_{q, m, β}问题.对于一个随机矩阵A∈Z_q^n×m，随机选择一个矩阵S∈{-d, …, 0, …, d}^m×k，计算T=ASmod q∈Z_q^n×k，发送(A, T)给. 需要模拟代理签名密钥预言机，模拟如下.

1) 代理签名密钥询问：对于代理签名用户id，计算U_id=H₃(id)，S_id=SU_id∈Z_q^m×l，把S_id发送给作为用户id的代理签名密钥.

当敌手在结束询问之后，输出矩阵S′，使得AS′=Tmod q，且S′∈{-d, …, 0, …, d}^m×k.要利用S′解决SIS_{q, m, β}问题.这里需要说明S′≠S.由引理1可知，至少以1-2^-100的概率存在另一个私钥S′(至少有一列与S不同)，使得AS′=AS.那么敌手输出的私钥与原私钥不同的概率至少是1/2，所以得到非零向量S-S′，且，使得A(S-S′)=0 mod q的概率至少是1/2.这样就解决了随机的SIS_{q, m, β}问题.

现在要证明任何人(包括代理签名者)在不拥有原始签名者私钥的情况下，不能够伪造代理签名密钥.现在需要利用敌手的能力解决SIS_{q, m, β}问题，对于一个随机矩阵A∈Z_q^n×m，随机选择一个矩阵S∈{-d, …, 0, …, d}^m×k，计算T=ASmod q.由于证明过程与上述类似，所以下面仅作简单的论述.如果敌手可以伪造代理签名用户id的代理签名密钥S′_id，那么T′_id=AS′_idmod q，T′_id=TU_idmod q，即AS′_idmod q=TU_idmod q.而则可以计算S_id=SU_id，那么

所以AS′_idmod q=AS_idmod q.由上面的讨论可知S_id-S′_id是SIS_{q, m, β}的一个小整数解.

下面来比较相关文献的代理私钥(不包括代理者自己的私钥以及所产生的签名)和代理签名的尺寸，结果如表 1所示.

表 1

表 1

表 1 相关方案比较

表 1 相关方案比较

其中，.对于参数d，σ，取d=1，.

在优化方案中，把原来的2个随机预言机合并为一个随机预言机，其输出长度为原来长度的和，如H₂:{0, 1}^*→{c:c∈{-1, 0, 1}^k+l, ‖c‖₁≤κ}，l＜k＜m.优化后可以提高近1倍的计算效率.其过程仅在代理签名上与初始方案不同.这里只给出代理签名过程.

代理签名：输入一个消息μ，代理者自己的私钥S₁，代理签名密钥S₂，签名如下：

① 选择一个向量y←D_σ^m；

② 计算c=H₂(Ay, μ)∈{-1, 0, 1}^k+l；

③ 计算z=(S₁‖S₂)c+y∈Z_q^m；

④ 以的概率输出(z, c).

公、私钥尺寸过大是目前格密码发展的一个瓶颈，而现有格上的代理签名方案中代理签名私钥的尺寸比原始签名者的私钥尺寸大得多.笔者提出了一个基于格上小整数问题的代理签名方案，通过降低代理签名私钥的维数来降低代理签名私钥的尺寸.但是在实际应用中，公、私钥尺寸还比较大，需要进一步降低尺寸.该方案在计算上主要使用的是矩阵乘法，与基于离散对数和分解大整数问题的方案相比，既不使用模指数运算，也没有配对运算，计算复杂度更低.