YC门限群签名方案分析及改进

彭娅

（广州大学华软软件学院，网络技术系，广州，510990）

摘要：Yuan-Lung Yu和Tzer-Shyong Chen提出的门限群签名方案不能抵抗内部成员的联合攻击，任何门限个成员联合可得到群私钥，从而不负责任地产生一个有效的群签名；改进的方案调整了私钥生成方法，其安全性基于求解离散对数问题的困难度，能抵御群内成员的联合攻击，具备可跟踪性。

关键词：门限签名；门限群签名；合谋攻击；离散对数；安全性

Cryptanalysis and improvement of YC Threshold group signature scheme

Peng Ya

（Department of Network Technology，South-china Institute of Software Engineering GZU，Guangzhou，510990）

Abstract： A threshold group signature proposed by Yuan-Lung Yu and Tzer-Shyong Chen could not resist the attack when some members conspired，any threshold members conspired to get group private key and forged aValid signature by irresponsible；By changing the way of key generation，the impoved scheme made the process of attack faced the difficulty of elliptic curve discrete logarithm，the impoved scheme that is based on the discrete logarithm problem can resist conspired attack，and it is contented of undeniable or unforgeability.

Key words： threshold signature，threshold group signature，conspired attack，discrete logarithm，security

1 引言

群签名方案允许组中合法参与者以群的名义签名，具有签名者匿名、只有权威才能辨认签名者等多种特点，在实际中有非常广泛的应用。在一个群签名方案中，任意一个成员可以以匿名的方式代表群体对消息进行签名。与其他数字签名一样，该群签名可以采用群公钥来验证。门限群签名是群签名的推广，一般的（t，n）门限群签名是指群内的t个或更多成员联合可代表群组签名，且签名成员的身份可查；而任何少于t个成员的联合则不能代表群组签名。这种签名技术结合了群签名和门限特性，签名的权力由多个成员掌握，具有门限签名的特点，但不能将门限签名和门限群签名等同起来。一般来说，门限群签名应具备以下性质：

（1）正确性：所有诚实的授权子集产生的签名必须能够通过验证；

（2）不可伪造性：只有群体中的合法成员才可以生成有效的部分签名；

（3）门限特性：只有当签名人数不小于门限值时，才可以生成有效的门限群签名；

（4）匿名性：签名的验证者不知道该签名是群体中哪些成员签署的；

（5）不可链接性：只能群管理员才能判断两个门限群签名是否由相同的授权组所签；

（6）抗陷害性：任何小组不能假冒其他小组生成门限群签名；

（7）可跟踪性：发生纠纷时可以追查出签名组成员的真实身份；

（8）抗联合攻击：任何小组不能产生不可跟踪的有效门限群签名。

与其他签名体制一样，门限群签名也需要寻求一个合适的密码体制作为其实现途径。自Desmedt和Frankel于1991年提出（t，n）门限群签名以来，门限群签名得到了广泛研究。结合门限群签名和椭圆曲线密码体制的优点，Yuan-Lung Yu等人在文献中提出了一个基于椭圆曲线离散对数问题的门限群签名方案，该方案具有较高的效率，且部分签名的验证和群签名的验证采用相同的协议，一定程度上减少了系统开销。但该方案无法抵御群内成员的合谋攻击，即当有门限个恶意成员联合时，可代表群进行签名，但群管理员无法追踪参与签名的成员的身份；本文通过改变私钥的生成方法，使得当门限个成员合谋时，无法产生一个不可追踪的群签名。

2 YC方案简介

YC门限群签名方案由CA（可信中心）选择系统参数和分发相关子密钥。整个方案由三个阶段组成：初始化、门限群签名的产生、门限群签名的验证。

2.1 初始化阶段

（1）CA产生并公布系统参数：

CA选择GF（p）上阶为q的椭圆曲线密码系统E：y2=x3+ax+b（modp），且公布如下系统参数：{E，p，q，h，G，xi（1≤i≤n）}。

其中p为大素数，p+1-2p1/2＜q＜p+1+2p1/2，a，b∈Zp，4a3+27b2≠0（modp）；h是单向哈希函数；G是椭圆曲线上阶为n的生成元；xi为群成员Ui的身份信息。

（2）CA秘密选择t-1次多项式f（x）：

f（x）=at-1xt-1+…+a1x+a0（modn）当i∈[1，t-1]时，ai∈[1，n-1]；其中f（0）=a0为群私钥，由群管理员GM保存；f（xi）为群成员Ui的私钥。

（3）CA计算N=-Y=-f（0）G，Ni=-Yi=-f（xi）G，分别作为群公钥和群成员Ui的公钥，并将其公开。

2.2 门限群签名产生阶段

假定现有一个群需签名消息m，不失一般性，设群内成员U1，U2，…，Ut可代表该群体为消息m产生一个有效的群签名。这个过程由个体签名、个体签名验证及合成（t，n）门限群签名等三部分组成。

（1）每个成员Ui选取随机数ki（1≤ki≤n-1），通过自己的私钥f（xi）为消息m产生部分签名：

成员Ui公开Ri，将个体签名（ri，si）送给签名合成者DC。

（2）DC收到（ri，si）后，通过以下等式检验个体签名的正确性：

Di=xDi（modn）

判断di=ri是否成立，若成立，则接受（ri，si）为有效的签名，否则签名无效。

（3）若所有的个体签名通过验证，DC为消息m产生群签名（r，s）。DC首先收集参与签名成员的Ri=（xi，yi），并计算

则门限群签名为（r，s）。

2.3 门限群签名验证阶段

任何接收者V收到（r，s）后，可用群公钥验证该签名的真实性。验证过程如下：

（1）接收者V首先计算，并判断S=s是否成立，如果成立则进行下一步的检验，否则签名无效。

（2）计算

判断l=r是否成立，若成立，则（r，s）是消息m的有效签名；否则，签名无效。

3 YC门限群签名方案的缺陷

YC方案不能抵抗联合攻击，即任意t个成员合谋可以伪造有效的群签名，而群管理员无法知道参与签名的成员身份。设t个成员构成的小组为I={I1，I2，…，It}，伪造过程如下：

（1）I中各成员Ii把私钥f（xi）发送给某个成员，设为T（T∈I），则T可通过Lagrange插值法重构t-1次多项式

（2）通过该多项式，T可计算F（0）=f（0）（modn）及F（xi）=f（xi）（modn）（i=1，2，…，n）。

（3）由此，这t个成员能够掌握其他所有成员的私钥f（xi）及群私钥f（0）。于是他们可以任意选择随机数k（1≤k≤q-1），令K=kG=（xK，yK），伪造签名（r’，s’）。其中的r’和s’分别计算如下：

该签名可以通过验证，验证过程的正确性证明如下：

因此，该方案中任意t个成员合谋能产生一个有效的门限群签名，一旦发生争执，群管理者也无法打开签名，也就无法追查签名的执行者，该方案不满足可追查性。

4 改进方案及分析

4.1 对YC方案的改进

为解决YC方案中的不可追查性，改进如下：

（1）在系统初始化阶段，对群成员的公私钥对以及群公私钥对的计算方式改进如下，其中系统参数的选择同2.1节。

CA秘密选择t-1次多项式f（x）：f（x）=at-1xt-1+…+a1x+a0（modq），当i∈[1，t-1]时，ai∈[1，n-1]；计算（xv，yv）=f（0）G=a0G，令v=xv为群私钥，由群管理员GM保存，N=-Y=-vG为群公钥；计算（xvi，yvi）=f（xi）G，令vi=xvi为群成员Ui的私钥，Ni=-Yi=-viG群成员Ui的公钥；将群公钥和群成员公钥公开。

（2）群签名的产生过程

① 每个成员Ui选取随机数ki（1≤ki≤n-1），通过自己的私钥vi为消息m产生部分签名：

成员Ui公开Ri，并将个体签名（ri，si）送给签名合成者DC。

② DC收到（ri，si）后，通过以下等式检验个体签名的正确性：

di=xDi（modn）

判断di=ri是否成立，若成立，则接受（ri，si）为有效的签名，否则签名无效。

③ 若所有的个体签名通过验证，DC为消息m产生群签名（r，s）。DC首先收集参与签名成员的Ri=（xRi，yRi），并计算

则门限群签名为（r，s）。

（3）群签名验证过程

任何接收者V收到（r，s）后，可用群公钥验证该签名的真实性。接收者计算L=（xL，yL）=sG+h（m）N，判断xL=r是否成立。若成立，则（r，s）是消息m的有效签名；否则，签名无效。

4.2 改进方案的安全性分析

这是一个具有（t，n）门限特性的群签名方案，需要t或t个以上的参与者才能代表某群体签名。对于外部攻击者而言，该方案是安全的：一方面如果某攻击者企图通过群公钥N=-vG来得到群私钥v，其困难性相当于椭圆曲线上离散对数问题的困难性，如果企图通过群成员Ui的公钥Ni=-viG来得到群成员Ui的私钥vi，其困难性相当于椭圆曲线上离散对数问题的困难性；另一方面，如果攻击者企图伪造一个个体签名，并能通过验证，仍将面临椭圆曲线上离散对数问题。

对于内部成员而言，改进后的方案能阻止恶意的t个成员联合攻击。仍设t个成员构成的小组，在改进的方案中，若I中各成员Ii把私钥vi发送给某个成员T（T∈I），T企图通过构造多项式来计算群私钥和群中其他成员的私钥是不可能的。

这是因为，T要构造，则必须知道至少t个f（xi），但是t个成员的联合，也只能让T得到t个vi，而vi=f（xi）G，要想通过vi来得到f（xi）是不可能的，因为这将面临解椭圆曲线上离散对数困难性。

5 总结

本文对Yuan-Lung Yu和Tzer-Shyong Chen提出的门限群签名方案进行了详细的密码学分析，指出该方案中任意t个成员合谋能产生一个有效的门限群签名，即不具备可追查性。对此文中进行了改进，通过改变私钥的生成方法，使得当t个成员合谋时，仍然无法得到群私钥和群成员的私钥，因此，改进后的方案解决了YC方案中t个成员联合攻击获取系统参数并伪造群签名的问题，具有椭圆曲线离散对数困难性。