基于离散对数的广义环签名算法

◆韩英帅 崔新春

（曲阜师范大学信息科学与工程学院 山东276826）

基于离散对数的广义环签名算法

◆韩英帅 崔新春

（曲阜师范大学信息科学与工程学院 山东276826）

广义环签名是一种具有可转换性质的特殊环签名。在必要的条件下，它允许真实的签名者通过透露关于环签名的一些秘密信息来把环签名转换为普通签名，从而撤销了签名的匿名性，证明自己就是签名者。2008年，Ren和Harn首次提出了基于ElGamal算法的广义环签名，并声称该签名方案是可转换的。后来，王化群等人通过论证分析证实了上述方案并不满足可转换性。通过进一步分析，本文还发现原广义环签名存在安全漏洞。为此，本文在原广义环签名的基础上加以改进，提出一种基于离散对数的广义环签名算法。改进后的新方案可以严格满足可转换性，并且安全性也得到了保障。

环签名；可转换性；合成函数；广义环签名

0 引言

目前，飞速发展的计算机技术和网络通信技术使人们的工作和生活发生了质的改变，电子商务、电子政务等信息化活动蓬勃发展。人们在畅享便利的同时，对信息安全技术的要求也越来越高。作为传统手工签名的替代品，数字签名已成为信息安全技术中一种重要的认证技术，在信息化活动中得到了广泛的应用。普通的数字签名仅用于保障信息传输中的数据认证性、完整性和不可否认性，这远远不能满足实际应用中的需求。针对特定的应用环境，催生了许多具有特殊性质的签名方案，如盲签名、代理签名、群签名、环签名[1-5]等。

2001年，Rivest等人[6]首次提出了基于RSA算法[7]的环签名。环签名因签名中的某些参数可以首尾连接形成环而得名。环签名允许一个成员代表一群成员进行匿名签名，在生成签名时，真实的签名者利用自己的私钥和其他环成员的公钥进行签名，但却不需要获得其他环成员的同意。对于任何一个验证者，他们都会相信信息已经被签名了，但是无法获知谁是真实的签名者。实质上，环签名是一类带有隐私考虑的类群签名，它可以被很好地用来保护真实签名者的身份，并克服了群签名[8]方案中群管理员权利过大的缺点。作为一项匿名泄密技术，环签名可以为需要长期保护的信息提供无条件的匿名性。目前，环签名技术己经广泛用于电子邮件、数据交换、电子交易和电子货币等领域[9-11]。

考虑到某些特定场景，尤其是在利益的诱使下，真实的签名者可能需要公布自己的身份。比如在匿名检举中，检举人想要检举某人但又不想让别人知道是自己所为，这时候他可以利用环签名来完成这一操作。一旦检举成功，检举人可能会获得丰厚报酬，那么他需要拿出不可否认的证据来证实自己的身份。为此，Lee等人提出了可转换的环签名[12]。

对比于环签名，可转换的环签名具有两大优势：（1）真实的签名者能够提供不可否认的证据来证实环签名由自己生成；（2）给定一个环签名和一个公钥集合，验证者能够证实该签名是否是某个环成员产生的有效环签名。

2008年，Ren和Harn[13]首次提出了基于ElGamal算法[14]的环签名(简称RH算法)。与基于RSA算法的环签名相比，RH算法做了如下改进：（1）全体环成员共享大素数p并且所有的计算都是在同一个域中进行的，因此可以避免扩展操作[6]；（2）通过联合多用户数字签名，广义多用户环签名可以用来实施跨组织参与的秘密信息泄露。这为信息的安全传输提供了更加强有力的保障；（3）RH算法是可转换的，即它允许真实的签名者通过透露不可否认的秘密信息来证实自己的身份。

但是，王化群等人[15]通过对RH算法的密码学分析，发现RH算法并不能满足可转换性，因为任意环成员都可以宣称对环签名的所有权。通过进一步分析，本文证实RH算法也不具备安全性。为此，本文将对RH算法加以改进，得到一种安全的基于离散对数的广义环签名算法。

1 RH方案概述及其漏洞分析

1.1 RH方案概述

在ElGamal算法中，p是一个大素数，g是中的生成元，并且 p、g被公开。签名者随机选取私钥 d ∈Zp-1，公钥由计算获得，私钥d需要严格保密。

给定需要被保护的信息 m，签名者随机选取一次性私钥

l∈ Zp-1，然后生成签名：

(α,β)即为 m的有效签名，其有效性可以通过等式（3）来验证：

相较于基于RSA算法的环签名，RH算法中的全体环成员共享大素数p，并且所有的计算都是在同一个域中进行的，因此RH算法不涉及扩展操作，这对应着RH算法的第一个改进之处。广义环签名的构建需要存在性伪造，而ElGamal算法正是一类带有通用报文攻击的存在性伪造算法[14，16]。在著名的双参数伪造签名过程中，真实的签名者给其他的环成员随机选取然后计算：

这样就得到了信息mi的一个有效签名

在RH算法中，假定存在一个抗碰撞的哈希函数h，即不存在两个不同的信息经过哈希函数处理后而得到相同的哈希值。下面，给出RH算法中的环签名算法和环验证算法。

图1 RH算法中的函数拓扑关系

Step1：Bs随机均匀地选取一个胶值（即初始值）v∈Zp；

Step3：为Bs设定下标签is，然后计算

上式中出现的下标签都属于Zn，因此有为了构成环，令则有该过程如图2所示。

图2 RH算法构成的环

Step5：生成环签名：

容易看出，m的环签名σ为一个(4n+2)元组。

环验证算法(m,)σ：对于环签名σ，验证者可以进行如下验证。

若成立，验证者认为环签名有效，否则拒绝。

1.2 RH环签名方案的漏洞分析

在RH算法中，作者宣称自己的环签名算法是可转换的。后来，王化群等人对 RH算法提出了一种攻击方法[15]。通过密码学分析，RH算法并不能满足可转换性，因为所有环成员都有能力宣称对环签名的所有权。本文通过进一步分析发现，RH算法缺乏安全性，这就说明RH算法不是安全可转换的。

如果Bi是真实的签名者，即Bi=Bs，不用通过计算，他就能知道sα的离散对数l，因为l是他自己随机选取的。因此他可以向验证者证实自己的身份，从而实现了环签名向普通签名的转换。然而，一旦泄露了真实签名者的秘密信息l，攻击者就会通过β的生成式：

计算出签名者的私钥ds。由此看来，RH环签名方案缺乏安全性。

如果Bi不是真实的签名者，即Bi≠Bs，他仍然可以宣称自己是真实的签名者。因为通过（3）式可以求得：

进一步就可以计算：

这样看来，其他环成员也可以通过提供li宣称自己是真实的签名者。

通过以上分析得出，RH算法既缺乏安全性，又不能满足可转换性。可见，RH算法存在严重的漏洞。

2 一种新的可转换的广义环签名算法

本文针对RH算法中出现的问题加以改进，得到一种新的可转换的广义环签名算法。

在改进过程中，本文继续沿用RH算法中的一些概念。具体步骤如下：

Step1：Bs随机均匀地选取一个胶值（即初始值）v∈Zp；

Step3：Bs随机选取r∈Zp，然后计算：

为Bs设定下标签is，并计算

上式中出现的下标签都属于Zn，因此有为了构成环，令则有

利用（8）式生成 mis的签名；

Step5：生成环签名：

新算法生成的环签名σ为一个(4n+3)元组。

环验证算法(m,)σ：对于环签名σ，验证者可以进行如下验证。

Step2：验证环等式：

若成立，验证者认为环签名有效，否则拒绝。

改进后的算法是可转换的，因为它可以满足环转环算法和环验证算法。

环转换算法：在需要公布自己隐匿身份的情况下，Bs可以通过透漏自己的秘密信息(r,x)把环签名转换为普通签名。

Step1：验证者首先验证（14）式是否成立。若成立，验证者可以通过比较和在es没有参加运算的情况下来指出Bs是真实的签名者。

环转换验证算法：获知了秘密信息(r,x)，验证者可以对环签名的有效性做如下验证：

Step1：验证者首先验证：

是否成立，若成立，则继续下一步验证，否则拒绝。

Step2：然后，验证者验证（14）和（16）是否成立，若成立，则接受环签名，否则拒绝。

3 算法分析

3.1 可转换性分析

本文基于RH算法加以改进，改进后的新算法严格满足可转换性，具体分析如下：

（1）无条件匿名性：新算法具有和 RH算法类似的功能，即能给真实的签名者提供无条件的匿名性。对于新算法生成的环签名σ，任意的都能满足（3）式。因为所有环成员之间的关系呈环状分布，所以能够满足环等式（18）。因此对于环外验证者来说，能够准确猜出真实签名者的概率不超过1/n，而环内非真实签名者能够准确猜出的概率不大于1/(n-1)。

（2）不可伪造性：在随机预言模型[13]（Random Oracle Model， ROM）中，任何伪造算法A（通过多项式次分析其他信息的环签名就可以以不可忽略的概率产生对于m'的环签名），都可以转换为新的算法 B（可以以不可忽略的概率对于随机的输入m'来求 fi的逆）。但是，本文设计的 fi是基于双线性映射对的。而对于双线性对的求逆，至今还没有找到切实可行的计算方法。因此，新方案满足不可伪造性。

（3）对于非真实签名者的不可转换性：如果Bi不是真实的签名者，即Bi≠Bs，他将不能证明自己是真实的签名者。即使Bi获知了Bs的秘密信息(r,x)，他会做如下计算：

通过以上分析，新算法满足了对于可转换的环签名的三条约束：无条件匿名性、不可伪造性和对于非真实签名者的不可转换性，故新算法是可转换的。

3.2 安全性分析

在RH算法中，真实的签名者一旦泄露了自己的秘密信息l，那么攻击者就可以通过（11）式来获得签名者的私钥ds。这一个环签名算法来说，显然是不允许的。本文对RH算法加以改进，以秘密信息(r,x)代替l。这样即使攻击者获得了秘密信息(r,x)，但由于哈希函数的单向性，他也无法获得签名者的私钥ds。由图3可知，l和ds都需要严格保密，二者有一个被获取，另一个也会被攻破。

图3 l和ds的关系

基于以上分析可以看出新算法是安全的。由于新算法是基于RH算法进行改进的，因此同样满足定理[13]：基于ElGamal算法的广义环签名对于ROM中的适应性选择消息攻击是安全的。

4 结束语

广义环签名允许在必要的条件下能够撤销真实签名者的匿名性，它是一种具有可转换性质的环签名。本文分析了RH算法，发现该算法不满足可转换性，而且存在安全漏洞。为此，本文对RH算法加以改进，改变真实签名者的秘密信息值，使新算法真正达到安全可转换的目的。最后，本文对新算法进行了可转换性分析和安全性分析，二者均达到了预期的要求。

[1]Bender A,Katz J,Morselli R． Ring signatures： Stronger definitions,and constructions without random oracles[C]//TCC，2006．

[2]Boyen X． Mesh Signatures：How to Leak a Secret with Unwitting and Unwilling Participants[J]．Eurocrypt，2007．

[3]杨华杰， 缪祥华， 朱海韬．一种高效无证书可追踪环签名方案[J]．信息安全与技术，2014．

[4]Fujisaki E，Suzuki K． Traceable Ring Signature[J]． IEICE Transactions on Fundamentals of Electronics Communications &Computer Sciences，2007．

[5]张春生，苏本跃，姚绍文．无双线性配对的无证书代理环签名方案[J]．计算机应用研究，2013．

[6]Rivest R L,Shamir A,Tauman Y．How to Leak a Secret[M]//Advances in Cryptology—ASIACRYPT，2001．

[7]Rivest R L．A method for obtaining digital signatures and public-keycryptosystems[J]．Communica tions of the Acm,1978．

[8]Harn L．Group-oriented (t,n) threshold digital signature scheme and digital multisignature[J]．IEE Proceedings - Computers and Digital Techniques，1994．

[9]Xiao J,Zeng G,Liao J,et al．Improved Threshold Ring Signature for Ad-Hoc Group[C]//International Conference on Wireless Communications, NETWORKIN G and Mobile Computing．IEEE,2006．

[10]Abe M,Ohkubo M,Suzuki K．1-out-of-n Signatures from a Variety of Keys[C]//International Conference on the Theory and Application of Cryptology and Information Security：Advances in Cryptology． Springer-Verlag,2002．

[11]Zhang F,Kim K．ID-Based Blind Signature and Ring Signature from Pairings[J]． Proc of Asiacrpt Lncs,2002．

[12]Lee,Wen,H-A,et al．Convertible ring signature[J]．Communications, IEE Proceedings,2005．

[13]Ren J,Harn L．Generalized Ring Signatures[J]．IEEE Transactions on Dependable & Secure Computing,2008．

[14]Elgamal T．A public key cryptosystem and a signature scheme based on discrete logarithms[J]．IEEE Transactions on Information Theory，2003．

[15]Wang H,Zhang F,Sun Y．Cryptanalysis of a Generalized Ring Signature Scheme[J]．IEEE Transactions on Dependable &Secure Computing，2009．

[16]Goldwasser S,Micali S,Rivest R L．A digital signature scheme secure against adaptive chosen-message attacks[M]．Society for Industrial and Applied Mathematics,1988．

教育部人文社科项目（No．11YJCZH021）；山东省自然科学基金面上项目（NO．ZR2016FM45）。