一个高效的无双线性对环签名∗

巫朝霞，张瑛瑛

(1.新疆财经大学应用数学学院，新疆乌鲁木齐830011;2.重庆邮电大学理学院，重庆400065)

0 引言

在电子商务中存在这样一个场景：一个公司的白领想要泄露公司的一些机密或是对公司不利的秘密，但是他又不想让其他人知道是他泄密，此时他应该怎么做呢？为了解决这类问题，Rivest等人[1]在2003年首先提出了环签名的概念．环签名在电子商务中具有很广泛的应用，比如隐私保护、投票选举等．环签名具有保护签名者身份的特点，也就是说任何人不可能根据签名追踪到签名者的真实身份．在一个环签名过程中，实际签名者是利用其他群成员的公钥和自己的私钥进行签名从而达到保护自己身份的目的．环签名是一种类群签名，但又与群签名不同，因为环签名既不需要管理者也不需要各成员之间的合作．迄今为止，许多研究者进行了相关工作研究[2]，如基于身份的环签名[3]、门限环签名[4]等．

Xu等人[5]在2004年，构造出一个环签名方案，他们的方案需要n+1个双线性运算和3n个指数运算．后来，Lv等人[6]提出了一个具有可恢复性特点的Schnorr环签名方案，该方案仅仅只需要3n个指数运算．最近，Shim[7]设计出一个高效的环签名方案，他们的方案只需要2个双线性运算和2n+1个指数运算．文献[5,7]对环签名进行了研究，并且得到了一些结果．但是在这些方案中均存在双线性对的使用造成了方案的成本很高的问题．设计出一个较少使用双线性对的密码方案在过去许多年一直是一个很重要的问题．因为使用双线性对越少，方案的成本也就会越低．本文给出一个高效和安全的环签名方案，此方案最大的优点就是在签名产生过程中不使用双线性对，并且我们的验证过程只需要一个哈希函数即可．最后在随机预言模型下证明了我们的环签名方案是不可伪造的．通过与其他环签名方案的分析对比，此方案比过去的一些方案具有更高的效率[5∼7]．

1 预备知识

1.1 双线性对

设G1为q阶循环加群，其中q为大素数，G2为具有相同阶的循环乘法群．我们称e:G1×G1→G2为一个双线对，如果它满足下列性质：

1.双线性性质:对所有的和有

2.非退化性:存在P,Q∈G1使得e(P,Q)ab=1；

3.可计算性:存在一个高效的算法计算e(P,Q)，其中P,Q为G1中任意两个元素．

本文安全性依赖于下列问题和假设．

定义1离散对数问题(DLP).设g=(E,+)，并且E是一个有限域Fl上的椭圆曲线，P∈E是一个具有素数阶q=|E|/2的点．设G1=(P)≤g，离散对数问题DLP就是给定aP∈G1，求出a的值．

定义2离散对数问题假设．设g是一个离散对数问题的参数生成者．我们说一个算法A有一个优势ε(k)解决离散对数问题就是对于g来说如果对于足够大的k有

给定一个上界时间限制T，我们说g满足离散对数问题假设是指对于任意的随机多项式时间算法A，Advg,A(k)是一个可忽略函数．当g满足DLP假设时，我们就称离散对数问题是在G1上困难的．

2 环签名标准定义和安全性模型

2.1 环签名标准定义

一个环签名可以分以下四个算法：初始化、用户密钥生成、环签名生成、环签名验证．算法的具体描述如下：

•初始化给定一个安全参数k，这个算法就输出一系列的系统参数；

•用户密钥生产用户使用(xi,Yi)作为他的私钥和公钥；

•环签名生成给定一个消息m，签名者选择其他n−1个用户组成一个群用户U，该算法就会代表群用户U生成一个对m的环签名σ；

•环签名验证给定一个消息m和一个环签名σ，以及n个用户的公钥Y1,...,Yn，如果σ是一个有效环签名，这个算法输出“接受”，否则“拒绝”．

2.2 环签名的安全性模型

在我们的环签名方案中，我们将考虑攻击者AI：AI不仅有n个签名者的公钥，而且有部分签名者的私钥．

游戏1对攻击者AI来说，SuccRS,AI定义为他和一个挑战者C在下述游戏1中成功的概率．

•初始化给定一个安全参数k，挑战者C运行初始化算法得到系统参数，然后挑战者C将系统参数发送给攻击者AI；

•哈希询问攻击者AI选择任意值，挑战者C返回相对应哈希值给AI；

•用户公钥询问攻击者AI选择并询问一个用户IDi的私钥，挑战者C返回相对应的公钥Yi给AI；

•私钥询问攻击者AI询问一个用户IDi的私钥，挑战者C返回相对应的私钥xi给AI；

•环签名询问攻击者AI选择并提交一个消息m，挑战者C返回相应的环签名σ给AI；

•伪造最后，攻击者AI输出另一个消息m∗的签名σ∗使得

1.σ∗是由攻击者AI生成的有效环签名；

2.m∗没有出现在环签名询问中．

定义3如果攻击者AI在最多时间T内，做最多qH次哈希查询，最多qU次用户公钥查询，最多qD次私钥查询，最多qRS次环签名查询后，AI可以攻破环签名，那么他成功的概率SuccRS,AI至少是ε．如果没有任何攻击者可以具有(T,qH,qD,qU,qRS,ε)攻破一个环签名，那么我们称该环签名在适应性选择消息攻击下是(T,qH,qD,qU,qRS,ε)存在性不可伪造的．

游戏2环签名的匿名性

设U=(u1,u2,...,un)是n个用户，在游戏2中，A是一个攻击者，C是一个挑战者．

•C执行初始化算法得到系统参数，并且发送给攻击者A．

• 攻击者A自适应性地做多项式限制次数环签名询问．

• 在挑战阶段，敌手输出一个消息m，n个用户的身份集W，两个不同的身份ID0,ID1∈W，并且把这些全部发送给挑战者C，挑战者C随机选择一个比特µ∈{0,1}，将环签名σ=RS(m,W,xµ)返回给攻击者A．

• 攻击者A自适应性地做多项式限制次数环签名询问．

• 最终，攻击者A输出比特µ ∈{0,1}．

敌手A在上面这个游戏成功当且仅当µ=µ．

定义4在游戏2中定义一个攻击者A成功的概率为：一个环签名具有无条件匿名性的前提是没有攻击者可以以不可忽略的概率优势在游戏2中获胜．或者说对于任意的多项式时间的攻击者，赢得游戏2的优势ε都是可忽略的．

3 本文的环签名方案

利用Schnorr签名的思想提出一个环签名方案．方案的参与者包括：n个用户U=(u1,u2,···,un)和一个验证者V．方案具体算法如下：

•初始化给定一个安全参数k，该算法输出(G1,q,P,H)．设G1是一个大素数q阶循环加群．设P是G1的生成元．设是一个安全密码哈希函数．

•用户密钥生成签名者随机选择作为她的私钥，计算对应的公钥为Yi=xiP．

•环签名生成给定一个消息m，n个用户的身份集一个实际签名者us可以为消息m匿名的产生一个环签名σ．实际签名者us做如下操作：

1. 签名者us随机选择．并且对所有的随机选择

2.计算h=

4.计算z=t−σsxs；

5. 输出σ=(σ1,σ2,...,σn,m,z)．

•环签名验证给定n个用户的公钥和一个环签名σ，一个验证者V可以用下面的等式验证环签名σ的有效性：

如果等式成立，验证者“接受”这个环签名，否则“拒绝”．

4 安全性分析

对环签名方案的不可伪造性和匿名性给出以下定理．

4.1 攻击者AI的不可伪造性

定理1在随机预言模型下，游戏1中攻击者AI可以适应性地选择消息攻击．假设在多项式时间T内，第二类攻击者做最多qH次H查询，最多qU次用户公钥查询，最多qD次私钥查询，最多qRS次环签名查询后，能以不可忽略的概率ε伪造一个有效的环签名．那么挑战者C就可以以优势来解决离散对数问题．

证明假如挑战者C接收到一个离散对数问题的随机实例(P,aP)，目的是计算出a的值．挑战者C设置签名者ID∗的公钥为：Y∗=aP．C是作为AI的子程序，并且在游戏1中扮演AI的挑战者．不失一般性，我们假设所有的询问都是不同的．现在，我们将展示挑战者如何回复攻击者AI的询问．

•H询问挑战者C有一个L列表(αi,hi)．这个列表初始是空的．当敌手AI做H(αi)询问时，挑战者C选择一个随机值hi，并设置H1(αi)=hi．然后挑战者C将(αi,hi)加到L列表中，返回hi给AI．

•用户公钥查询挑战者C有一个LU列表(IDi,xi)．这个列表初始是空的．当攻击者AI对身份IDi做公钥询问时，挑战者C选择一个随机值xi∈Z∗q，设置Yi=xiP．然后挑战者C将(IDi,xi)加到列表中，返回Yi给攻击者AI．

•私钥查询当攻击者AI对身份IDi做私钥询问时，如果IDi=ID∗，那么C立刻停止操作．否则挑战者C回复相应的私钥值xi给AI．

•环签名询问AI提交一个消息m和n个用户的身份集W={ID1,ID2,···,IDn}．C如下输出一个环签名．如果一个用户身份IDs∈W满足IDsID∗，那么挑战者C执行签名算法来回复签名σ，其中IDs是真正的签名者．否则，挑战者C执行如下步骤：

1. 选择随机t∈Z∗q，并且对所有i∈(1,2,···,n) 随机选择σi∈Z∗q；

3.设置z=t；

4. 输出σ=(σ1,σ2,···,σn,m,z)．

伪造敌手AI输出一个消息m∗的环签名σ∗，必须满足如下条件：

1.σ∗是AI输出的有效环签名；

2.伪造的环签名σ∗不是来自签名询问的．

输出由分叉引理得：如果攻击者AI在时间TA内可以给出一个有效的伪造签名．那么，我们可以构造另一个算法，在时间2TA内，以至少的概率对两个消息签名．用类似构造，挑战者C可以得到相同的结果，σ和σ是两个有效的环签名．

挑战者C输出

概率根据交叉引理，如果攻击者AI可以以ε的概率成功，那么挑战者C在游戏1中就能以至少的概率解决离散对数问题的一个实例．

4.2 无条件匿名性

定理2我们的环签名具有签名者无条件匿名性，也就是说对于任意算法A，任意一组用户集U=(u1,u2,···,un) 和一个随机的us∈U，概率其中是一个由us生成的环签名．

证明

•C执行初始化算法得到系统参数，并且发送给攻击者A．

•攻击者A自适应性地做多项式限制次数环签名询问．

• 在挑战阶段，敌手输出一个消息m，n个用户的身份集W，两个不同的身份ID0,ID1∈W，并且把这些全部发送给挑战者C，挑战者C随机选择一个比特µ∈{0,1}，将环签名σ=RS(m,W,xµ)返回给攻击者A．

•攻击者A自适应性地做多项式限制次数环签名询问．

• 最终，攻击者A输出比特

环签名方案中，由于t,σi是随机地从中选择，则σs是上一个的随机元．由于t是随机地从中选择，则z是上的随机元．不论谁是真正的签名者，对于包含这个签名者的任意一组用户集U，任一消息m，签名σ=(σ1,σ2,···,σn,m,z)的分布都是独立和均匀分布的．也就是说任何人都没有优势知道真正的签名者的身份．因此，环签名满足了匿名性．

5 效率

把本文的方案与其他相关方案进行计算复杂性的对比．不考虑G1中的加法运算和哈希函数运算所消耗的时间（因为耗时非常的少），剩下就只有三种主要的运算：双线性对运算、椭圆曲线群G1上的数乘运算以及ZN下的模指数运算．下面定义几个符号：

•PO:双线性配对运算；

•TE:基于ECC的数乘运算；

•TN:在ZN下的模指数运算.

仿真过程中使用MIRACAL函数库方法得到以上密码运算的运行时间．硬件平台是带有512 M字节内存和Windows XP操作系统的PIV 3 GHZ处理器．表1显示了每个密码运算的平均时间．对于基于配对的协议，为了达到1024位RSA级别的安全性，我们使用嵌入度为2的超奇异椭圆曲线E/Fp:y2=x3+x.q是160位Solinas素数q=2159+217+1，p是一个512位的素数．对于基于ECC的协议，为了达到相同的安全级别，我们在F2163上定义的Koblitz椭圆曲线y2=x3+ax2+b上使用了ECC组，其中a=1且b为163位随机素数．最终每个运算的运行时间列于表1．

表1 操作时间(单位：毫秒(ms))

为了评估不同方案的计算效率，我们使用文献[8]中的简单方法．例如，方案[5]需要n+1个双线性对运算和3n个ZN的模指数运算，所以方案[5]的运行时间就是：(n+1)×20.01+3n×11.20=53.61n+20.01．为了便于比较，我们设n=10，那么方案[5]的执行时间就是：53.61×10+20.01=556.11ms.根据上述参数设置和方式，几种不同的环签名方案的详细比较结果如表2．从表2可以看出，我们的方案更加高效．

表2 几个环签名对比

6 结束语

本文利用Schnorr签名的思想提出了一个可以保护实际签名者身份的环签名方案．在随机预言模型下利用离散对数问题证明了本文方案是不可伪造的．且将该方案与之前的一些环签名方案做了对比，发现该方案具有更高效率．鉴于以上两种优势，本文环签名方案在当今电子商务中应用前景广泛，具有高效性、安全性和不可伪造性．