基于国密SM9算法的门限环签名方案

邓浩明，彭长根,3，丁红发，叶延婷

(1.贵州大学 计算机科学与技术学院，贵州 贵阳 550025；2.贵州大学 公共大数据国家重点实验室，贵州 贵阳 550025；3.贵州大学 密码学与数据安全研究所，贵州 贵阳 550025；4.贵州财经大学 信息学院，贵州 贵阳 550025)

0 引 言

当前，许多敏感隐私数据需依托网络进行传输，这对传输数据的安全提出了很高的要求。目前绝大多数传输系统利用密码技术来保证数据的隐私安全，但数据签名者的身份并没有得到很好的保护，这会导致数据发送方与接受方存在身份泄露的安全问题。

环签名[1]的提出能够解决签名者的身份隐私问题，可以确保环内签名者的身份实现匿名化。一个环签名方案包含n个自发组成环的签名者，环中签名者首先使用私钥对消息进行签名，其次利用公钥验证签名的有效性。环签名已有广泛的应用，如车载物联网[2]、自动泊车系统[3]、第六代移动通信技术(6G)[4]、区块链[5]等场景。

在环签名的基础上，Bresson等[6]提出第一个门限环签名方案，其主要原理是预先设置一个门限值t，只要任意t个环成员进行签名，就可得到最终签名结果。该方案利用公平拆分的思想将环成员进行公平拆分，在随机预言模型下证明了方案的安全性，但签名的效率随着签名者数量的增加而降低。文献[7]利用消息块共享技术提出了一种基于格的门限环签名方案，但该方案在消息比特长度较大时，签名生成与验证的效率较低。文献[8]通过将随机因子引入到用户的属性密钥中，提出了一个可变门限环签名方案，其实现了具有抗合谋攻击的安全特性，但方案的签名长度较长，验证效率较低。文献[9]提出一个利用分布式密钥生成协议解决属性密钥托管问题的门限环签名方案。巧妙利用身份标识的特性，使方案的安全性得到进一步的加强。此外，该方案提出了一种批验证方法，能够有效提高验证的效率。文献[10]将门限环签名应用于区块链上，提出了一种可以将过期区块数据删除的可删除区块链方案，利用门限值的特性，提高删除区块的效率。

Shamir首次提出基于身份的密码体制(IBC)[11]，IBC可以将用户的身份标识作为公钥，同时也不需要额外的数字证书，因此在不同场景下得到了广泛的应用。文献[12]首先提出一种基于身份的环签名方案，该方案的双线性配对运算较多，因此在计算效率上有一定的劣势。文献[13]基于公平拆分的思想，提出了一种基于身份的(t,n)门限环签名方案，但在签名生成与验证阶段需要多次使用双线性对运算，所以效率较低。文献[14]提出两种基于身份的门限环签名方案，在该方案中，任何t个环成员可以代表n个环成员生成一个合法的门限环签名。但该方案需要n倍次数的双线对运算，其总效率具有的优势并不明显。文献[15]提出一种可以利用基于原始消息生成的环签名，去派生原始消息子串上的新环签名的方案，由于该方案需要多次指数运算，其在总体计算开销上效率较低。文献[16]将门限环签名与可否认认证协议相结合提出一种非交互式可否认(t,n)门限环签名方案，其可以确保签名的真实身份不被泄露，但无法抵御选择消息攻击。文献[17]提出一个在格上基于模糊身份的环签名方案，该方案可以实现对真实签名者的身份进行审计与监督，并在随机预言模型下证明了方案的安全性，但仍存在签名效率不高的问题。文献[18]提出一个基于SM9算法的环签名方案，但在签名生成和验证阶段需n倍次数的双线对运算，方案总体计算开销效率较低。

综上所述，现有方案没有很好地同时解决环签名的效率与方案的安全性等问题。为了解决上述问题，该文利用强抗碰撞性的SM3算法[19]对n-t次多项式的常数项进行优化处理，并生成256 bit的杂凑值；利用SM4算法[20]资源消耗率较低和加解密效率高的优势，对门限环签名进行对称加密，并在密文中嵌入具有时效性的时间戳，提高了签名的安全性；最后，将文献[7]中的门限参数提取算法进行改进，并把生成的门限值t引入SM9签名算法中，使得签名效率得到提高，并利用SM9算法[21]加密强度大、系统资源消耗率较低、无需申请数字证书和广泛应用性[22-23]等优势，将SM9数字签名算法作为底层密码技术基础，最终生成安全高效的门限环签名。

在随机预言模型下证明了GMTRS方案具有适应性选择消息攻击下的不可伪造性，并具有匿名性、抗重放攻击性和前向后向安全性等优势。效率分析表明，GMTRS方案相较于现有环签名方案，在签名生成和验证效率上分别具有约52.38%和32.16%的效率提升。同时所提方案的门限值t的变化，对方案的总开销影响基本可忽略，故GMTRS方案在安全性与效率上具有一定的优势。

1 基础知识

1.1 双线性对

设G1和G2是阶为素数N的加法循环群，GT是阶为素数q的乘法循环群，P1和P2分别为G1和G2的生成元。定义在群上的一个双线性映射关系e:G1×G2→GT，并且满足以下的性质：

(2)非退化性：对∃U∈G1,∃V∈G2，满足e(U,V)≠1。

(3)可计算性：对∀U∈G1,∀V∈G2，存在一个有效的算法在多项式时间内计算e(U,V)的值。

1.2 困难问题假设

定义1：离散对数问题(DLP)。给定椭圆曲线E上任意两点P,Q，给定等式aP=Q，在多项式时间内a是不可解的。

1.3 环签名相关概念

门限环签名方案[6]的一般模型由以下4个阶段组成。

初始化：输入安全参数γ，输出公共参数P和系统主密钥Kpub。

密钥生成：输入(P,Kpub)，输出签名者的公私钥对(pki,ski),i∈[1,N]。

签名生成：输入公共参数P，消息m，门限值t，n个环成员的公钥集合P={pk1,pk2,…,pkn}和所对应的私钥集合ε={sk1,sk2,…,skn}，输出环签名σ。

签名验证：输入公共参数P，消息m，门限值t，n个环成员的公钥集合P={pk1,pk2,…,pkn}和所对应的私钥集合ε={sk1,sk2,…,skn}以及环签名σ，返回验证结果接受或拒绝。

基于身份的门限环签名方案[13]的一般模型由以下4个阶段组成。

初始化：输入随机数π，输出主密钥K和系统参数Para。

签名生成：输入消息m，n个签名者的身份标识IDi∈{0,1}*,i∈[1,n]，t个签名者的私钥SKi，输出一个关于消息m的基于(t,n)门限值的环签名σ。

签名验证：输入环签名σ，消息m，门限值t和n个签名者身份标识IDi∈{0,1}*，如果n个签名者中至少有t个成员对消息m签名，则返回验证结果为有效；否则，返回结果为无效。

1.4 门限环签名安全性定义

本节主要介绍门限环签名的安全模型，门限环签名方案必须满足以下条件。

定义2：正确性。如果t个以上的签名者按照签名步骤生成环签名σ，则环签名σ能通过验证。

定义3：强不可伪造性。假如有n个环成员，在其中任意选取个数不小于t个的环成员，就可代表环进行签名。如果攻击者A在概率多项式时间内选择任意消息M(除M'以外)并询问相应的签名结果后，成功伪造一个签名的概率仍是可忽略的，则门限环签名方案满足适应性选择消息攻击下的不可伪造性。

定义攻击者A成功伪造门限环签名的优势为：

GMTRS方案的不可伪造性可以通过以下游戏进行正式定义：

初始化阶段：已知n个环成员的身份标识集合ID={ID1,ID2,…,IDn},i∈[1,n]，其中挑战者C运行KeyGen算法获得n个环成员的公私钥对MK1=(ski,pki),i∈[1,n]，并将环成员的公钥pki发给攻击者A。

询问阶段：攻击者A可以自适应地执行哈希询问、私钥询问、签名询问。

(1)哈希询问：攻击者A向挑战者C要求获取关于消息M的哈希值。

(2)私钥询问：攻击者A选择任意环成员的身份标识IDi发送给挑战者C，挑战者C计算相应的私钥ski返回给攻击者A。

(3)签名询问：攻击者A选择消息M，门限值t，发送给挑战者C，挑战者C运行Sign并生成消息M相应的门限环签名σ。

(1)验证(M',σ')=true。

(2)签名伪造者的身份标识IDi∈ID,i∈[1,t]。

(3)没有执行签名算法而生成(M',σ')。

定义4：匿名性。在门限环签名方案中，超过t个以上的签名者参与签名，并最终生成门限环签名σ。但攻击者不知道是哪t个签名者参与了门限环签名的生成。

2 基于国密SM9算法的门限环签名方案

GMTRS方案包括初始化、密钥生成、环签名生成、环签名加密、环签名验证五个阶段。在初始化阶段之前，GMTRS方案使用Choi和Kim提出的门限参数提取算法[7]，生成环n和门限t的值。但该算法在消息长度很短时，无法生成相应的参数，从而导致无法生成门限环签名。因此，先对消息的位长进行处理，将短消息用0 bit填充到λbit宽度，将长消息压缩到λbit宽度。其中，由于方案选取的曲线是阶为256 bit的BN曲线，所以方案的λ长度设置为256 bit。最后，输入填充后的消息，生成环n和门限值t的值。

2.1 初始化

Setup(λ)→(MK,Para)

2.2 密钥生成

KeyGen(λ,ID,ran)→(Ke,MK1)

输入安全参数λ，n个环成员的身份标识集合ID={ID1,ID2,…,IDn}，主私钥ran。

(1)KGC选择Ke←{0,1}λ作为SM4分组密码算法的对称密钥。

(3)输出对称加密密钥Ke，环成员的公私钥对MK1=(pki,ski)。

2.3 环签名生成

Sign(Para,M,t,Pmpk,R,U)→(σ)

输入公共参数Para，消息M，门限值t，主公钥Pmpk，环签名成员的私钥集合R={ski},i∈[1,n]，其私钥所对应的公钥集合U={pki},i∈[1,n]，设{1,2,…,t}为参与签名的环成员索引，不参与签名的环成员索引为d∈{t+1,t+2,…,n}，签名生成具体的步骤如下：

(1)计算g=e(P1,Pmpk)；

(2)对于d∈{t+1,t+2,…,n}，随机选择rd,hd∈[1,N-1]；计算Zd=grd，Td=[Zd]skd；

(3)对于j∈{1,2,…,t}，随机选择uj∈[1,N-1]，计算Zj=guj；

(4)将Zd,Zj的数据类型转换为比特串，并计算h0=H0(U‖t‖M‖Z1‖Z2…‖Zn,N)；

(5)计算L=(uj-h0)modN，若L=0则返回步骤(2)，重新选择随机数；

(6)对于d∈{t+1,t+2,…,n}，构造一个n-t次多项式fd(x)=hdxn-t+…+h2x2+h1x+h0，其中，

hd=H0(pkd‖n-t‖M‖Zt+1‖Zt+2…‖Zn,N)，

f(0)=h0，f(d)=hd；

(7)当j∈{1,2,…,t}，计算hj=f(j)，Sj=[uj-hj]skj；

(8)输出关于消息M的(t,n)门限环签名σ=(t,S1,S2,…,St,Tt+1,Tt+2,…,Tn,f)。

2.4 环签名加密

Enc1(σ,M,Ke,η)→(Eσ,EM)

输入环签名σ，对称密钥Ke，时间戳η，使用SM4分组加密算法，对消息M和环签名σ进行加密，并嵌入时间戳η，输出密文消息EM和加密环签名Eσ。

Enc2(pki,Ke)→(EKe)

输入环成员的公钥pki，对称密钥Ke，输出加密的密钥EKe。

2.5 环签名验证

Dec1(EKe,ski)→(Ke)

输入环成员的私钥ski，加密的密钥EKe，输出对称密钥Ke。

Dec2(Ke,EM,Eσ)→(M',σ')

Verify(Para,Pmpk,M',σ',t,U,ID)→

(accept,reject)

输入公共参数Para，消息M'，门限值t，主公钥Pmpk，n个环成员公钥集合U，环签名σ'，n个环成员的身份标识集合ID={ID1,ID2,…,IDn}，签名验证具体的步骤如下：

(1)检查消息M'和环签名σ'中时间戳η的时效性，如果无效则拒绝该消息验证失败；否则继续执行；

(2)验证多项式f是否为n-t次，如果不是，则验证失败；

(4)计算g=e(P1,Pmpk)，vj=gf'(j)；

(8)验证h'=f'(0)是否成立，若成立则签名合法，则输出“accept”；若不成立，则输出“reject”。

3 安全性分析

3.1 方案的正确性

定理1：GMTRS方案的门限环签名满足正确性。

证明：在门限环签名验证时，需要验证h'=f'(0)是否成立。

因为，

e([uj-hj]skj,[ci]P2+Pmpk)=

e(([uj-hj][t2]P1),[ci]P2+[ran]P2)=

e(P1,P2)(uj-hj)[t2](ci+ran)=

e(P1,P2)(uj-hj)[ran]

(1)

又因为，

vj=gf'(j)=e(P1,Pmpk)hj=

e(P1,[ran]P2)hj=

e(P1,P2)hj[ran]

(2)

则：

w'=vj·zj=

e(P1,P2)(uj-hj)[ran]·e(P1,P2)hj[ran]=

e(P1,P2)uj[ran]=e(P1,[ran]P2)uj=

e(P1,Pmpk)uj=Z

(3)

3.2 方案的不可伪造性

定理2：在随机预言模型中，如果DLP问题具有难解性，则GMTRS方案具有适应性选择消息攻击下的不可伪造性。

证明：给挑战者C一个DLP问题的挑战实例(P1,aP1)，C的目标是利用敌手A的能力伪造出有效的门限环签名，并最终计算出a。在随机预言模型下，密码杂凑函数H0,H1被当作随机预言机。

初始化：挑战者C执行Setup算法获得系统参数Para和主密钥对MK，并将系统参数Para发送给攻击者A。

询问阶段：攻击者A执行自适应询问，挑战者C设置L0、L1、L2和L3列表去存储询问结果。其中，列表L0中储存哈希H0询问结果，列表L1中储存哈希H1询问结果，列表L2中储存私钥询问结果，列表L3储存签名询问结果。

(1)哈希H0询问：当A询问H0(U‖t‖M‖Z1‖Z2…‖Zn,N)时，C首先在L0中检查H0的询问记录。若询问记录不存在，C将随机选择ci∈[1,N-1]，并设置H0(U‖t‖M‖Z1‖Z2…‖Zn,N)=ci，并以((U‖t‖M‖Z1‖Z2…‖Zn,N),ci)的格式存储到L0中。

(2)哈希H1询问：攻击者A发送给挑战者C一个环成员的身份标识IDi，同时询问H1(IDi‖χ,N)，C首先在L1中检查其询问记录。若记录不存在，C将随机选择yi∈[1,N-1]，设置H1(IDi‖χ,N)=xi，并将((IDi‖χ,N),xi)存储到L1中。

(4)签名询问：攻击者A任意选择消息M、门限值t和主公钥Pmpk发送给挑战者C，C执行Sign算法生成门限环签名σ，并将(M,t,σ)储存到L3列表中。如果生成签名过程中发生哈希碰撞，则需要重新执行生成门限环签名的步骤。

(4)

(5)

所以，

(6)

(7)

因此DLP问题的挑战实例(P1,aP1)可解，由于DLP难解性可知其与假设相矛盾，所以GMTRS方案在随机预言模型中具有适应性选择消息攻击下的不可伪造性。

3.3 方案的匿名性

定理3：GMTRS方案具备匿名性。

3.4 方案的前向与后向安全性

定理4：GMTRS方案满足前向与后向安全性。

证明：密钥生成中心(KGC)重新选择随机数ran来确定系统的主私钥，根据重新确定的主私钥来确定系统的主公钥Pmpk，并将更新的主密钥对MK=(ran,Pmpk)发送给环成员，同时KGC也会记录之前的主密钥对，用来验证之前签名的有效性。因为ran是KGC随机选取的，所以ran具有随机性，从而系统参数Para也具有随机性，所以攻击者A不能伪造出之前的主密钥对。即使A成功伪造出主密钥对，其也无法融入到环成员中，也无法伪造出门限环签名，所以GMTRS方案满足前向与后向安全性。

3.5 方案的抗重放攻击性

定理5：GMTRS方案中的门限环签名具备可抗重放攻击性。

证明：GMTRS方案在已签名的门限环签名σ和消息M的密文中嵌入一个时间戳η。在验证签名之前，首先将检查时间戳η的时效性。如果攻击者A截获合法生成的门限环签名或消息两者其中的一个，在验证签名时，时间戳的新鲜度检查将失败，则该门限环签名σ'或消息M'将被拒绝，导致签名验证流程结束，故GMTRS方案生成的门限环签名具备可抗重放攻击性。

4 效率分析

将GMTRS方案与文献[12-14，16,18]进行计算开销对比，主要从私钥生成、签名生成和签名验证三个方面来比较，因为这三个部分所占的计算开销较大。其中主要比较双线性配对运算B和幂运算E的运算次数，因为双线性配对运算和幂运算所需要消耗的计算资源较多，同时忽略一些计算成本很小的运算。其中包括使用SM4算法对环签名进行对称加解密运算，GMTRS方案只需要进行两次加密运算和两次解密运算，并且所需的计算开销与环成员个数n和门限值t的大小无关，根据表3中给出的单次加解密运算所消耗的时间大小，环签名加解密阶段所需的计算成本基本可以忽略。

GMTRS方案使用嵌入度为12的BN曲线E:y2=x3+5，其中阶为256 bit的大素数N。选择长度为256 bit的相应参数能保证方案具有与长度为3 072 bit的RSA密钥相当的安全强度。相关运算符号含义如表1所示，计算开销对比如表2所示。

表1 运算符号含义

表2 不同环签名方案计算开销

由表2可知，GMTRS方案只需进行一次计算成本可忽略的哈希运算H和计算成本较小的一次标量点乘运算M就可生成私钥；在签名生成阶段，GMTRS方案需要进行一次双线性配对运算B、n次幂运算E和n次标量点乘运算M，同时相较于效率较高的文献[16]，其所需要的双线性配对运算与标量点乘运算的运算次数明显均要多于本方案；在签名验证阶段，GMTRS方案需要进行双线性配对运算、幂运算和标量点乘运算的次数只与门限值t有关，由门限环签名的特性可知t

为了进行更加直观的对比，本文在3.20 GHz的8核64位Intel(R)Core(TM) i5-10210处理器、8 GB RAM和Windows 10操作系统的计算机上进行了实验。基于表1相同的数据设置，并采用Miracl密码函数库进行实验操作，得到表1中相关运算的单次运算所消耗的时间。同时调用SM4对称加解密算法对1 024字节长度的字节串进行加解密实验操作，并以循环执行1 000次加解密取平均值的方式，得出SM4单次对称加解密所消耗的时间，实验结果如表3所示。

表3 相关运算单次运算消耗时间

本文以群体医疗咨询背景为例，没有设置过大的环成员数，按照实际情况将n设置为10，t设置为6。其中n为专家医生的人数，在上述相同的实验环境下，分别进行了签名阶段和签名验证阶段的时间开销对比实验，实验结果如图1和图2所示。

图1 签名生成时间开销对比

由对比可得，GMTRS方案对比文献[12-14,16,18]具有较高的签名生成效率，并且相较于耗时最短的文献[16]，在签名阶段效率提升约52.38%。对比效率较高的文献[18]，GMTRS方案签名验证阶段效率得到约32.16%的提升。GMTRS方案在签名生成阶段与签名验证阶段的效率均占有一定优势，具有更好的实用性。

图2 签名验证时间开销对比

由于签名效率会受到门限值t和环成员n大小变化的影响，所以以大规模签名场景为例，在相同的实验环境下，进行了n与t变化的对比实验，结果如图3和图4所示。

图3 总开销下t变化时间开销对比

图4 总开销下n变化时间开销对比

图3和图4实验结果表明，GMTRS方案的总开销与t和n的大小变化呈线性关系，但所提方案的曲线波动幅度较小。由图3可知，因为文献[12]与文献[18]是环签名方案，所以门限值t的变化不会导致签名开销变化。但在n和t相等时，GMTRS方案为全部环成员都参与签名的环签名方案，方案总体效率仍为最高。由如图4可知，当门限值t大小固定n增加时，方案的总体时间开销最小。综上，GMTRS方案在签名生成阶段与验证阶段的效率均具有优势，具有更好的实用性。

5 结束语

在环签名的基础上，加入了(t,n)门限值，利用国密算法作为底层密码技术支持，提出了一种基于国密SM9算法的门限环签名方案(GMTRS)。GMTRS方案只需要t个以上的签名者对消息进行签名，就可以代表所有环成员得到最终的签名。并将国密算法与门限环签名相结合，既保留了环签名的特性，又提高了签名的效率和安全性。在随机预言模型下证明了适应性选择消息攻击下的不可伪造性，同时GMTRS方案也具有不可匿名性和抗重放攻击性等优势。效率分析表明，GMTRS方案在计算开销和效率上相较现有方案具有明显的优势。此外，该方案仍然需要计算成本高的双线性对运算，下一步需要考虑如何减少双线对运算次数等问题，使方案的效率更高。