基于(t, n)门限的变色龙数字签名方案

郑明辉

(湖北民族学院 计算机科学与技术系，湖北 恩施 445000)

(t,n)门限签名方案是一种面向群的签名方案[1,2]，在规模为n的群中只有参与签名成员的数目大于或等于门限值t时才能生成有效的群体签名，而当成员少于t-1个时，则无法完成群体签名.此类签名方案在开启银行的保险箱、电子投票系统等方面有着广泛的应用. 然而，门限签名方案使用Lagrange插值多项式导致了较高的计算开销[3]，另外，门限签名方案还需通过交互的方式实现签名有效性的验证，导致验证所需的通讯及计算成本增加[4]，因此此类签名方案的实用性收到一定的局限.

Chaum and Antwerpen首次提出了不可否认签名的概念[5]，随后Chaum又提出了零知识不可否认签名[6].而Lee,Krawczyk 等人[7,8]所提出的变色龙签名方案则是不可否认签名方案的变体，变色龙签名方案基于一种特殊的哈希函数，称为变色龙哈希(Chameleon hash)，正由于这种特殊的哈希函数，变色龙签名方案具备非交互性、不可传递性和不可否认性等优良特性.由于变色龙签名方案不需透过交互的方式进行签名的有效性验证，可以在签名验证阶段节省通讯及计算成本，因此本文通过将变色龙哈希函数引入门限签名方案，提出一种基于门限的变色龙数字签名方案，该方案克服了门限签名方案需通过交互的方式实现签名有效性验证的不足，减少了签名的复杂度，提高了签名的效率.

1 门限变色龙签名方案设计

在提出新的签名方案之前，先简要介绍签名者产生签名时所使用的变色龙哈希函数及其特性.变色龙哈希函数的形式为CHAMh(m,R)=gmYrRmodp，其中m为签名方传送的消息，R为计算变色龙哈希函数所需要的随机数，Yr为签名接收方的公钥.一个安全的变色龙哈希函数必须具备以下三个安全特性：其一，抗碰撞性(Collision resistance).即只拥有签名接收者的公钥时无法计算出(m′、R′)使得其变色龙哈希值会等同于原先(m,R)所计算出的变色龙哈希值，也就是无法算出(m′、R′)使得CHAMh(m′,R′) =CHAMh(m,R)；其二，门限碰撞性(Trapdoor collisions).签名接收者可利用自已所拥有的私钥，任意选取(m′、R′)，使得其变色龙哈希值等同于原先(m,R)所计算出的变色龙哈希值，也就是利用签名接收者私钥即可算出(m′,R′)使得CHAMh(m′,R′) =CHAMh(m,R)；其三，均匀性(Uniformity).在计算变色龙哈希函数时使用的随机数被选中的概率是相同的，同时当使用此随机随机数时，不会泄露所要传送的变色龙哈希值的相关信息.

本文设计的基于门限的变色龙签名方案由系统参数生成、密钥生成、签名生成和签名验证等四个阶段组成，各阶段的详细描述如下.

1.1 系统参数生成阶段

假定有n个用户参与签名：U1,U2…..Un，最低门限值为t，首先利用一可信中心生成系统所需的相关参数：

p：为一安全大素数，范围为p≥2512；q：可将p-1整除的素数，范围为q≥2160；

g∈Zp：为Zp的生成元；CHAMh：为gmYrRmodp，指变色龙哈希函数计算方法.

1.2 密钥生成阶段

该阶段分别生成个体和群体的签名公私钥对：

Step 1.Ui在[1,q]中随机选择的公开值xi；

Step 2.Ui在[1,q]中随机选择的秘密值si；

Step 3.Ui根据Yi=gSimodp计算自己的个体签名公钥Yi并广播给其它签名参与者；

1.3 签名生成阶段

假设有t个用户参与对消息m的签名过程，同时事先指定一个签名合并者(可在t个用户中事先随机指定一签名者为签名合并者)，该签名合并者将所有个体签名者所产生的变色龙哈希值及变色龙部分签名合并为群体的变色龙哈希值及群体变色龙签名，此阶段包括如下步骤：

Step 1. 每个签名参与者Ui先随机选取一个随机数ri∈Zq*，再利用此ri及接收方公钥Yr计算CHAMhi=gm/tYrrimodp，然后将计算的CHAMhi传送给签名合并者；

Step 2. 当签名合并者收到t个CHAMhi后，按下式计算CHAMh：

然后签名合并者将计算所得的CHAMh传送给每个参与者Ui；

Step 3. 当参与者Ui收到CHAMh后，首先计算：

再将计算出来的αi传给签名合并者；

Step 4.当签名合并者收到t个αi后，计算α：

则(CHAMh,α)为消息m的签名.

1.4 签名验证阶段

该阶段验证所收到的签名是否为有效签名.假定(CHAMh,α)为消息m的签名，则可通过下面计算对签名结果进行验证：

签名接收者首先计算W=gα*YCHAMhmodp，再用自己的私钥sr验证下式是否成立：

CHAMh=(gm*Wsr)modp

若上式成立，则表示该签名接收者接收到的签名为消息m的合法签名，即可信任此消息m之内容；反之，若验证式不成立，则表示签名者接收到的签名为非法签名.

2 安全性分析

由于变色龙哈希函数具有抗碰撞性，所以攻击者无法伪造出消息签名对(m′,R′)使得其变色龙哈希值等同于原来的(m,R)所计算出的变色龙哈希值，也就是无法使得等式CHAMh(m′,R′)=CHAMh(m,R)成立，故攻击者是无法由已知的明文及相关数字签名信息来伪造正确的数字签名.

本文提出的数字签名方案是以Krawczyk and Rabin所提出的变色龙数字签名方案为基础，此方案具有不可否认性、不可转移性及解决签名者与接收者之间争议等安全特性，所以提出的数字签名方案也具有相同安全特性.而签名者公私钥的安全性是基于离散对数的困难性，攻击者是无法根据群体签名的公钥推出群体签名的私钥，同样地，签名者个体私钥也被离散对数所保护，无法根据签名者个体公钥将签名者的个人私钥推导出来，故无论是群体签名的私钥还是签名者个体私钥都不会被攻击者计算出来.

另外，(t,n)门限数字签名方式利用Lagrange插值多项式来计算群体签名，当少于t个签名者时，将无法恢复出群体签名的私钥，不能进行签名有效性的验证.此外，在提出的数字签名方案中，每个参与的签名者都清楚自已所签署消息m的内容，并只有将自已所签署的部份签名发送给签名的合并者后，才能进行最后的群体签名，这样签名方法，对于小于t个用户的合谋攻击而言，可以有效预防.

3 结语

结合Krawczyk and Rabin所提出的变色龙数字签名方案和Lagrange插值多项式，提出了一种基于门限的变色龙数字签名方案，该方案可应用于有可信中心或无可信中心的环境.提出的方案不但具有不可否认性、不可转移性、抗合谋攻击等特性，而且签名接收者可通过非互动的方式进行签名验证，降低了门限签名方案的计算复杂度.

[1]Minghui Zheng, Jianhua Zhu, Guohua Cui.A(t,n) threshold signature scheme against conspiracy attack[C]//Proceeding of ICT ，2006:219-223.

[2]郑明辉, 王小非, 崔国华，等. 一种公钥自认证的(t,n)门限签名方案[J].华中科技大学学报:自然科学版,2007,35(11):99-102.

[3]Harn L.Group-oriented (t,n) threshold digital signature scheme and digital multisignature[C]//Computers and Digital Techniques,IEE Proceedings,1994,141(5):307-313.

[4]Harn L,Yang S.Group-oriented undeniable signature schemes without the assistance of a mutually trusted party[C]//ASIACRYPT,1992:133-142.

[5]Chaum D,Antwerpen H V.Undeniable Signatures[C]//CRYPTO,1989：212-216.

[6]Chaum D. Zero knowledge undeniable signatures[C]//EUROCRYPT,1990:458-464.

[7]Lee N Y,Hwang T.Group-oriented undeniable signature schemes with a trusted center[C]//Computer Communications,1999,22(8):730-734.

[8]Krawczyk H,Rabin T，Chameleon Signatures.Processing of Network and Distributed System Security Symposium 2008[C]//IEEE Computer Sciety,2008:143-154.