一个新的有向门限签名方案

文小华，王相金，沈忠华

（杭州师范大学理学院，浙江杭州310036）

一个新的有向门限签名方案

文小华，王相金，沈忠华

（杭州师范大学理学院，浙江杭州310036）

提出了一个新的有向门限签名方案，在该方案中，用户共享秘密由两部分组成，一部分是SDC中心发送给用户的，另一部分是用户自己秘密选取的.因此，该方案可以抵御系统人员的攻击，也可抵御n个用户的合谋攻击，满足了有向性和门限的性质，并利用交互式的零知识证明向第三方证明了群签名的有效性.

有向签名；门限；零知识；拉格朗日插值公式

0 引 言

数字签名是现代信息安全保障体系中最重要的技术之一.在传统的数字签名中，任何拥有签名的人都可以利用签名者的公钥验证签名的有效性，这一特性对于文件的散发是必须的，但在有些情况下，签名的消息对于接受者而言是比较敏感，或是比较隐私的，如汇票、医疗记录、税务信息等.此时就需要保证消息上的签名只有消息接受方才能验证，任何第三方需要验证此签名的有效性都必须与接受者合作才能完成.这样的签名称为有向签名［1］.然而在有些特殊情况下，签名的消息需要征求一个群体中大多数人的同意，而且消息对接受者来说是敏感的，不能在公开场合散发和验证，为了解决此问题，就产生了有向门限签

名［2－4］.

一个标准的有向门限签名必须满足以下几个要求：1）一个n成员组成的群组中，任意t个成员或者更多的成员能为一个指定的验证者生成一个群签名，而少于t个成员则不能生成签名；2）指定的验证者只需要签名者的公钥和自己的密钥就能直接验证群签名的有效性，其他人并不能验证签名；3）第三方必须在指定验证者的帮助下才能完成对签名有效性的验证.本文利用拉格郎日插值公式［5］设计了一个门限签名方案，同时结合Schnorr［6］签名体制和ELGamal［7］公钥理论提出了一种新的有向门限签名方案.

1 方案描述

本文提出的有向门限签名方案包括以下几个部分：系统参数初始化、群密钥和秘密共享的产生、部分签名和群签名的生成、指定接受者的验证和第三方的验证.设G＝｛u1，u2，…，un｝为n个用户所组成的集合，ui为每个用户的身份标识，ui≠uj（i≠j）.H为G的一个子集，H中包含t个用户，并假定有一个可信的秘密共享分配中心（share distribution center，SDC）用于产生公共参数和秘密共享.假定H中的用户想为用户B在消息m上签名，并事先约定一个大家认可的群签名合成中心（designated combiner，DC）用于收集H中所有成员的部分签名.

1.1 系统参数初始化

1）SDC选择g1，g2∈z＊p，p为一个大素数；

2）SDC选择一个单向的哈希函数h（·）.

1.2 群密钥与共享秘密的产生

1）SDC选择一个s作为系统的群密钥，每个用户Ui选择一个xi作为自己的秘密值，并秘密保存.计算yi＝gx1imod p，yi作为用户的公钥公开.

2）用户Ui选择一个随机数t，计算T＝gt2mod p，然后将（yi，T）发送给SDC；SDC计算

将（B′，C）在公开信道上发送给Ui，当用户Ui收到（B′，C）后计算自己的共享秘密

由此用户Ui的密钥为两部分：一部分是SDC发送给用户的，另一部分是用户自己秘密选择的一个值

3）SDC设一个任意的n次多项式f（x）＝a0＋a1x1＋a2x2＋…＋anxnmod p，然后将（0，s），（u1，ys1），（u2，ys2），…，（un，ysn）代入多项式得到一个方程组：

通过解同余方程组即可确定f（x）.

选择随机数m1，m2，…，mn＋1－t，然后作如下计算：

计算Ti＝g1mimod p，且公布（Ti，γ1，γ2，…，γn＋1－t）.

4）群签名的指定接受者R选择自己的密钥xR，并计算YR＝g1xRmod p，TixR＝Δimod p，将YR发送给SDC，SDC收到后计算YSR＝F.

5）公开参数〈g1，g2，yi，F，ui，Δi，Ti，γ1，γ2，…，γn＋1－t〉.

1.3 部分签名和群签名的生成

假设群组中t个成员（设这些成员构成一个组H）同意为R对消息m签名，不妨设这t个成员Uj1，Uj2，…，Ujt拥有共享秘密分别为（Gj1，xj1），（Gj2，xj2），…，（Gjt，xjt），并做如下标记：

2）每个成员Uji计算自己的部分签名

将部分签名（Eji，Vji，χji，Ψ）发给群签名合成中心DC.

3）DC收到用户Uji的部分签名后计算群签名.

是否相等.如果不相等，退出签名；如果相等，部分签名有效，则继续计算

由此生成群签名为（E，Ψ，W，M，ϑi）.

1.4 指定接受者R和第三方C验证签名的有效性

1）指定的接受者R验证签名的有效性.

当收到群签名后，R利用自己的密钥xR验证下式是否成立：

如果等式成立，R接受签名，否则退出.

2）第三方C验证签名的有效性.

如果第三方C想验证签名的有效性，必须在指定验证者R的帮助下才能完成.

首先，R计算

将（E，Ψ，W，M，ϑi）和（u，Z）发送给第三方C，由C检查Ψ＝h（Z｜W｜M）是否相等.如果不相等，退出验证；如果相等，则继续下面的步骤.

指定验证者R以交互式的零知识方式向C证明logzu＝logYg1R，证明步骤如下：

a）R随机选择一个整数t，计算R1＝gt1mod p，R2＝utmod p，将R1，R2发送给C；

b）C选择一个随机整数K，将K发送给R；

c）R计算ω～＝t－K·xR，再将ω～返回给C；

d）C验证R1＝g1YKRmod p，R2＝u ZKmod p是否成立.如果两个式子都成立，则C就验证了签名的有效性.

2 方案一些等式的证明

定理1 当ui≠uj（i≠j）时，同余方程组（1）一定存在唯一的解，且多项式f（x）＝a0＋a1x1＋a2x2＋…＋anxnmod p成立.

证明 由于ui≠uj，所以有

由同余克拉默法则［8］，只要满足D≠0mod p，（D，p）＝1时，方程组有且仅有唯一解，故可以确定唯一的f（x）.

定理2 如果部分签名Eji为合法的，则等式g1Eji＝Vjiχji－Ψϑi mod p成立，否则不成立.

证明

定理3 如果签名合法，则等式Ψ＝h（YERFΨWxR（∏ΔiΨϑi）mod p｜W｜M）必然成立.

i＝t＋1

证明

3 安全性分析

1）t个人或者更多的人合谋无法求出群密钥S.假定n个人合谋共享他们的部分密钥ysi和身份标识ui，则将（ysi，ui），1≤i≤n代入式（1）中无法求出ai（0≤i≤n），故无法重构多项式f（x），因此n个人合作无法得出群密钥S＝f（0）.假定任意t合谋，同时利用公开的（γi，Ti），也无法求出S，因为Ti＝g1mi mod p，而解mi是一个求解离散对数问题，故无法得到mi；又因为γi＝f（i）＋mi，1≤i≤n＋1－t，因而不能求解f（i），那么任意t个人无法利用（ysji，uji），1≤i≤t和（f（i），i），1≤i≤n＋1－t在式（1）中重构出f（x），故不能求解出群密钥S.

2）抵御系统人员的攻击.任意用户Ui的共享秘密由两部分组成：一部分是用户自己选择的一个秘密数xi，外人无法得知；另一部分是SDC发送给用户的ysi.这样可以抵御SDC冒充用户的攻击.同时本方案的共享密钥发放是在公开信道上进行的.

3）在部分签名阶段，敌手无法伪造部分签名Eji.因为

且Ki1，δi，xji都是未知的，部分签名Eji无法确定.

4）少于t个成员无法生成群签名，满足门限的性质.

根据式（4），如果成员少于t人，那么故群签名的验证肯定通不过.

5）敌手得到一个合法的群签名（E，Ψ，W，M，ϑi），不可能验证它，满足有向签名的性质.

因为从YR＝g1xRmod p，TixR＝Δimod p求解xR是一个离散对数问题.故敌手无法得知xR并验证

4 结 论

本文提出了一种新的（t，n）有向门限签名方案，该方案与以往的一些有向门限签名方案［2－4］相比具有更高的安全性：1）在文献［2－4］中，用户的秘密份额全部由SDC中心产生，因此SDC知道每个用户所持有的秘密份额，这样就不能抵抗内部人员的攻击.在本方案中，通过用户自己选择一个秘密数xi解决了内部攻击问题；2）在文献［2－4］中，秘密共享方式是Shamir门限体制或者Asmuth－Bluoom体制，这种方式下，只要t个人合谋就能恢复主密钥，系统也就不具有安全性.在本方案中，改进了Shamir门限体制，通过用户提供的（ui，ysi）和SDC提供的（0，s）合作来确定多项式f（x），从而使得t个人或者更多的人合谋无法求出主密钥S；3）本方案满足有向性和门限的性质；4）本方案中利用交互式的零知识证明向第三方C证明了群签名的有效性.可见，本方案解决了以往一些方案存在的安全问题，增强了有向门限签名方案的安全性.

［1］Lim C H，Lee P J.Modified Maurer－Yacobi's scheme and its applications［J］.Lecture Notes in Computer Science，1993，718：308－323.

［2］沈忠华，于秀源.一个安全有效的有向门限签名方案［J］.浙江大学学报：理学版，2006，33（4）：393－395.

［3］Lu Rongxing，Lin Xiaodong，Cao Zhenfu，et al.New（t，n）threshold directed signature scheme with provable security［J］.Information Sciences，2008，178（3）：756－765.

［4］沈忠华.基于中国剩余定理的（t，n）有向门限签名方案［J］.浙江大学学报：理学版，2010，37（1）：42－45.

［5］Shamir A.How to share a secret［J］.Communications of the ACM，1979，22（11）：612－613.

［6］Schnorr C P.Efficient signature generation by smart cards［J］.J of Cryptology，1991，4（3）：161－174.

［7］Gamal T.A PKC and a signature scheme based on discrete logarithm［C］／／IEEE trans information theory.New York：Springer－Verlag，1985：469－472.

［8］段炼.同余式组的“Cramer规则”问题［J］.河南师范大学学报：自然科学版，1998，26（3）：88－90.

A New Directed Threshold Signature Scheme

WEN Xiao－hua，WANG Xiang－jin，SHEN Zhong－hua
（College of Science，Hangzhou Normal University，Hangzhou 310036，China）

This paper presented a new directed threshold signature scheme.In the scheme，the sharing secrets of users are composed of two parts，one part comes from SDC，and the other part is selected in private by users.Therefore，the scheme can resist the attack from the system staff as well as the conspiracy attack from the users.It can satisfy directed and threshold properties，and prove the validity of group signature to third party with interactive zero－knowledge proof.

directed signature；threshold；zero－knowledge；Lagrange interpolation formula

TP309 MSC2010：94A60

A

1674－232X（2012）03－0259－05

10.3969／j.issn.1674－232X.2012.03.014

2011－11－15

沈忠华（1973—），男，副教授，主要从事数论与密码学、信息安全技术、电子商务等研究.E－mail：ahtshen＠126.com