一个前向安全的结构化多重签名方案

付竟芝，斯桃枝，周振江

（1. 南京人口管理干部学院信息科学系，南京 210042；2. 上海第二工业大学计算机与信息学院，上海 201209）

一个前向安全的结构化多重签名方案

付竟芝1，斯桃枝2，周振江1

（1. 南京人口管理干部学院信息科学系，南京 210042；2. 上海第二工业大学计算机与信息学院，上海 201209）

基于有限域上计算离散对数的困难性，将前向安全的概念引入到结构化签名方案中，提出了一个新的具有前向安全性质的结构化签名方案。该方案同时具有一般结构化签名和前向安全签名的特点。

前向安全；数字签名；结构化数字签名

0 引言

结构化数字签名[1-2]是一种特殊的多重数字签名，即在签名的过程中每个签名成员必须按照预先规定好的顺序签名，签名的顺序是固定不变的。完成多重数字签名的全体成员构成了一个群组。成员签名的顺序称为群组的结构，群组的结构有顺序结构、并行结构和混合结构。顺序结构是指在签名时，群组中的成员按照顺序方式执行签名；而并行结构是指群组成员可以按任意顺序执行签名协议；混合结构是将以上两种结构混合而得到的群组结构。结构化签名的产生和验证都依赖于群组的结构，如果成员不按照指定的结构进行签名，就不会得到有效的签名。一个签名的前向安全性是将签名的有效时间分割成多个签名周期，在每个签名周期开始时，群组的全体成员同时使用密钥更新算法产生新周期的签名密钥，而验证签名的公钥在整个有效时间内都不改变。当第j个周期的密钥暴露时，前向安全的签名方案能够保证前面的j −1个周期内的签名的有效性。实现前向安全性主要是依赖求模大素数乘积的平方根难题，依据该难题设计出了许多具有前向安全性的签名方案[4-6]。本文将前向安全性的概念引入到结构化多重签名中，提出了一个ELGamal类型的前向安全的结构化签名方案。该方案不仅实现了结构化签名，而且也满足了签名前向安全的特性。

1 ELGamal类型的前向安全的结构化签名方案

假设群组G由n个成员组成，G = {P1, P2,…, Pn}。群组G的结构是顺序结构，是指成员签名的顺序为顺序方式签名，即P1→P2→P3→…→Pn；群组G为并行结构是指P1, P2,…, Pn可以按任意顺序完成签名；群组G为混合结构则是指有部分成员是并行结构，其它成员构成顺序结构。

1.1 系统参数

选择三个大素数p, p1和p2, 使得p = 2p1p2−1, 令N = p1p2, g是Zp的生成元,是安全的单向Hash函数。签名密钥的有效期分为T个时间段，即1, 2,…, T。

1.2 顺序结构时成员Pi(i=1,2,…, n) 和群组的公钥和私钥产生

Pi(i = 1, 2,…, n) 随机选取作为他的初始私钥，其公钥yi的计算为

1.3 顺序结构时成员Pi的签名私钥更新算法

第j+1个周期的签名密钥由以下公式计算得到

1.4 顺序结构签名的生成

群组中的成员Pi(i = 1, 2,…, n)，随机取一个数ki，并计算r=(y)kimodp( i=1,2,…,n)，其中y=g，

ii+1n+1并在群组中广播ri。当群组中的每个成员收到全部的ri后，计算R=r1r2…rnmodp 和Y=H( M, j, R)，其中M是签名消息，j是周期数。再按P1→P2→P3→…→Pn的顺序计算si(i=1,2,…,n)

其中0sY=。当Pi(i = 1, 2,…, n)在计算si之前可以通过如下验证方程来验证si−1的有效性

如果验证方程不成立，Pi终止签名；如果验证方程成立，则说明si−1是正确的。则群组的签名为(R, s)，其中s=sn。

1.5 顺序结构签名的验证

验证者先计算Y=H( M, j, R)，再验证以下方程是否成立

如果签名通过验证方程，则关于消息M的签名(R, s=sn)是一个有效的前向安全的结构化签名。如果签名的计算过程没有按前面的顺序进行，则验证方程是不成立的。因为1.6 混合结构时签名的产生

在混合结构中，不妨假设P1, P2,…, Pi−1组成顺序结构，Pi是由m个并行签名的成员组成，设为pi,1, pi,2, …, pi,l, 而Pi+1,…, Pn还是顺序结构，从总体上看，群组中的成员还是顺序结构，为了描述方便，用Pi表示m个并行签名的成员。Pi的签名实际上就是由并行签名得到。在混合结构中的系统参数与顺序结构相同，首先群组G的成员按以顺序结构的方式产生它们的公钥和初始私钥。Pi的m个成员Pi,l(l=1,2,…,m)，随机选取奇数作为它的初始私钥，它的公钥为

则Pi对应的。si满足以下验证方程

当Pi计算出自己的ri和si时，群组G的其它成员Pi+1,…, Pn可以按照顺序结构签名的操作步骤计算出它们自己的签名，则混合结构的签名为(s, R)，其中s=sn。混合结构的签名验证方程和顺序结构的验证方程相同。

2 安全性分析

（1）无法从Pi的第j个周期的密钥推导出第j+1个周期的密钥因为面临求解模p平方根的难题；也无法从公钥中解出签名成员的初始签名密钥，因为这会遇到解离散对数的难题。

（2）如果群组成员不按规定的顺序生成签名(R′, s′)，根据验证方程可知，该签名是无法通过验证方程的，所以文中提出的签名方案满足结构化签名的要求。

（3）由于在每个不同的周期，群组成员的签名密钥都是不同的，当第j个周期的签名密钥被暴露时，要想利用第j个周期的签名密钥来伪造前面的签名，就必须推出第j−i ( i=1, 2,…, j−1) 个周期的签名密钥，这就面临了求解模p平方根的难题，所以保证了前面各周期签名的有效性。

（4）伪造一个签名是不可能的，因为在签名的过程中需要整个群组成员的私钥和公钥信息，部分成员来伪造一个有效的签名是不可行的。

3 结束语

群签名是一种多人对同一个消息进行的一种签名。在实际工作中的一些特殊的部门可能需要多个人对同一个消息进行签名，这就需要多重签名。多重签名的顺序可能相同，也可能不同，那么不同的签名顺序就是不同的签名结构。标准的多重签名存在一个固有的弱点，那就是：一旦所有参与者的密钥泄漏，所有的多重签名（包括产生在密钥泄露之前的签名）都不可信任了。因此，如何减小密钥泄漏的危害是一项重要的研究工作。前向安全签名可以减小密钥泄漏的危害，将系统的整个生命周期划分成若干个时间段，每个时间段都通过单向的演化函数演化新密钥，并删除以前的旧密钥，而公钥在整个生命周期中保持不变。即便当前的密钥泄漏了，以前时间段的签名仍然是有效的。同时，在这种情况下不同的签名结构可以对应不同部门的需要，这样可以满足许多部门的不同的需求，节省部门的资源，提高签名的效率。结构化的多重签名就是在这种需求下提出的。这种特殊签名的使用可以大大提高签名的速度，提高工作效率。因此这是一种有一定实际应用价值的特殊签名。

本文将前向安全的概念引入到结构化签名方案中，构造了一个新的ELGamal类型的前向安全的结构化签名方案，它不仅保持了结构签名的特点，并且又具有前向安全的性质，在计算方面没有大的增加，其安全性要比一般的结构化签名更高。

[1] BURMESTER M, DESMEDT Y, DOI H, et al. A structured ElGamal-type multisignature scheme[J]. Proceedings of Third International Workshop on Practice and Theory in Public Key Cryptosystems (PKC 2000), Springer-Verlag, 2000, 1751: 466-483.

[2] HARN L, LIN C Y, WU T C. Structured multisignature algorithms[J]. IEE Proceedings, Computers and Digital Techniques, 2004, 151(3): 231-234.

[3] ITAKURA K, NAKAMURA K. A public-key cryptosystem suitable for digital multisignature[J]. NEC Research and Development, 1983, 71: 1-8.

[4] MICALI S, OHTA K, REYZIN L. Accountable-subgroup multisignatures: extended abstract[C]//Proceedings of the ACM Conference on Computer and Communications Security 2001 (CCS2001), New York: ACM Press, 2001: 245-254.

[5] BELLARE M, MINER S K. A forward-secure digital signature scheme[J].Wiener M J, Advances in Cryptology-CRYPTO’99, Lecture Notes in Computer Science, 1999,1666: 431-448.

[6] BELLARE M, YEE B. Forward security in private key cryptography[J].Joye M, Topics in Cryptology-CT-RSA 2003, Lecture Notes in Computer Science, 2003, 2612: 1-8.

A Forward-Secure structured Multisignature Scheme

FU Jing-zhi1, SI Tao-zhi2, ZHOU Zhen-jiang1
( 1. Department of Information Science, Nanjing College for Population Programm Management, Nanjing 210042, P. R. China; 2. Institute of Computer and Information, Shanghai Second Industrial University, Shanghai 201209, P. R. China )

Based on the difficulty of computing discrete logarithm over finite field of large prime order, forward-secure technique is introduced into structured multisignature signature, then a new structured multisignature scheme with forward-secure is presented. It has not only characteristic of general structured multisignature, but characteristic of forward-secure .

forward security; data signature; structured multisignature

TN918.91

A

1001-4543(2012)03-0187-04

2012-04-18;

2012-08-30

付竟芝（1964－），女，黑龙江人，高级统计师，学士，主要研究方向为计算机网络，电子邮箱fujingzhi1964@163.com。