一個新的有向門限簽名方案

文小華，王相金，沈忠華

（杭州師范大學(xué)理學(xué)院，浙江杭州310036）

一個新的有向門限簽名方案

文小華，王相金，沈忠華

（杭州師范大學(xué)理學(xué)院，浙江杭州310036）

提出了一個新的有向門限簽名方案，在該方案中，用戶共享秘密由兩部分組成，一部分是SDC中心發(fā)送給用戶的，另一部分是用戶自己秘密選取的.因此，該方案可以抵御系統(tǒng)人員的攻擊，也可抵御n個用戶的合謀攻擊，滿足了有向性和門限的性質(zhì)，并利用交互式的零知識證明向第三方證明了群簽名的有效性.

有向簽名；門限；零知識；拉格朗日插值公式

0 引 言

數(shù)字簽名是現(xiàn)代信息安全保障體系中最重要的技術(shù)之一.在傳統(tǒng)的數(shù)字簽名中，任何擁有簽名的人都可以利用簽名者的公鑰驗證簽名的有效性，這一特性對于文件的散發(fā)是必須的，但在有些情況下，簽名的消息對于接受者而言是比較敏感，或是比較隱私的，如匯票、醫(yī)療記錄、稅務(wù)信息等.此時就需要保證消息上的簽名只有消息接受方才能驗證，任何第三方需要驗證此簽名的有效性都必須與接受者合作才能完成.這樣的簽名稱為有向簽名［1］.然而在有些特殊情況下，簽名的消息需要征求一個群體中大多數(shù)人的同意，而且消息對接受者來說是敏感的，不能在公開場合散發(fā)和驗證，為了解決此問題，就產(chǎn)生了有向門限簽

名［2－4］.

一個標(biāo)準(zhǔn)的有向門限簽名必須滿足以下幾個要求：1）一個n成員組成的群組中，任意t個成員或者更多的成員能為一個指定的驗證者生成一個群簽名，而少于t個成員則不能生成簽名；2）指定的驗證者只需要簽名者的公鑰和自己的密鑰就能直接驗證群簽名的有效性，其他人并不能驗證簽名；3）第三方必須在指定驗證者的幫助下才能完成對簽名有效性的驗證.本文利用拉格郎日插值公式［5］設(shè)計了一個門限簽名方案，同時結(jié)合Schnorr［6］簽名體制和ELGamal［7］公鑰理論提出了一種新的有向門限簽名方案.

1 方案描述

本文提出的有向門限簽名方案包括以下幾個部分：系統(tǒng)參數(shù)初始化、群密鑰和秘密共享的產(chǎn)生、部分簽名和群簽名的生成、指定接受者的驗證和第三方的驗證.設(shè)G＝｛u1，u2，…，un｝為n個用戶所組成的集合，ui為每個用戶的身份標(biāo)識，ui≠uj（i≠j）.H為G的一個子集，H中包含t個用戶，并假定有一個可信的秘密共享分配中心（share distribution center，SDC）用于產(chǎn)生公共參數(shù)和秘密共享.假定H中的用戶想為用戶B在消息m上簽名，并事先約定一個大家認(rèn)可的群簽名合成中心（designated combiner，DC）用于收集H中所有成員的部分簽名.

1.1 系統(tǒng)參數(shù)初始化

1）SDC選擇g1，g2∈z＊p，p為一個大素數(shù)；

2）SDC選擇一個單向的哈希函數(shù)h（·）.

1.2 群密鑰與共享秘密的產(chǎn)生

1）SDC選擇一個s作為系統(tǒng)的群密鑰，每個用戶Ui選擇一個xi作為自己的秘密值，并秘密保存.計算yi＝gx1imod p，yi作為用戶的公鑰公開.

2）用戶Ui選擇一個隨機(jī)數(shù)t，計算T＝gt2mod p，然后將（yi，T）發(fā)送給SDC；SDC計算

將（B′，C）在公開信道上發(fā)送給Ui，當(dāng)用戶Ui收到（B′，C）后計算自己的共享秘密

由此用戶Ui的密鑰為兩部分：一部分是SDC發(fā)送給用戶的，另一部分是用戶自己秘密選擇的一個值

3）SDC設(shè)一個任意的n次多項式f（x）＝a0＋a1x1＋a2x2＋…＋anxnmod p，然后將（0，s），（u1，ys1），（u2，ys2），…，（un，ysn）代入多項式得到一個方程組：

通過解同余方程組即可確定f（x）.

選擇隨機(jī)數(shù)m1，m2，…，mn＋1－t，然后作如下計算：

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

4）群簽名的指定接受者R選擇自己的密鑰xR，并計算YR＝g1xRmod p，TixR＝Δimod p，將YR發(fā)送給SDC，SDC收到后計算YSR＝F.

5）公開參數(shù)〈g1，g2，yi，F(xiàn)，ui，Δi，Ti，γ1，γ2，…，γn＋1－t〉.

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

假設(shè)群組中t個成員（設(shè)這些成員構(gòu)成一個組H）同意為R對消息m簽名，不妨設(shè)這t個成員Uj1，Uj2，…，Ujt擁有共享秘密分別為（Gj1，xj1），（Gj2，xj2），…，（Gjt，xjt），并做如下標(biāo)記：

2）每個成員Uji計算自己的部分簽名

將部分簽名（Eji，Vji，χji，Ψ）發(fā)給群簽名合成中心DC.

3）DC收到用戶Uji的部分簽名后計算群簽名.

是否相等.如果不相等，退出簽名；如果相等，部分簽名有效，則繼續(xù)計算

由此生成群簽名為（E，Ψ，W，M，?i）.

1.4 指定接受者R和第三方C驗證簽名的有效性

1）指定的接受者R驗證簽名的有效性.

當(dāng)收到群簽名后，R利用自己的密鑰xR驗證下式是否成立：

如果等式成立，R接受簽名，否則退出.

2）第三方C驗證簽名的有效性.

如果第三方C想驗證簽名的有效性，必須在指定驗證者R的幫助下才能完成.

首先，R計算

將（E，Ψ，W，M，?i）和（u，Z）發(fā)送給第三方C，由C檢查Ψ＝h（Z｜W｜M）是否相等.如果不相等，退出驗證；如果相等，則繼續(xù)下面的步驟.

指定驗證者R以交互式的零知識方式向C證明logzu＝logYg1R，證明步驟如下：

a）R隨機(jī)選擇一個整數(shù)t，計算R1＝gt1mod p，R2＝utmod p，將R1，R2發(fā)送給C；

b）C選擇一個隨機(jī)整數(shù)K，將K發(fā)送給R；

c）R計算ω～＝t－K·xR，再將ω～返回給C；

d）C驗證R1＝g1YKRmod p，R2＝u ZKmod p是否成立.如果兩個式子都成立，則C就驗證了簽名的有效性.

2 方案一些等式的證明

定理1 當(dāng)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和身份標(biāo)識ui，則將（ysi，ui），1≤i≤n代入式（1）中無法求出ai（0≤i≤n），故無法重構(gòu)多項式f（x），因此n個人合作無法得出群密鑰S＝f（0）.假定任意t合謀，同時利用公開的（γi，Ti），也無法求出S，因為Ti＝g1mi mod p，而解mi是一個求解離散對數(shù)問題，故無法得到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）中重構(gòu)出f（x），故不能求解出群密鑰S.

2）抵御系統(tǒng)人員的攻擊.任意用戶Ui的共享秘密由兩部分組成：一部分是用戶自己選擇的一個秘密數(shù)xi，外人無法得知；另一部分是SDC發(fā)送給用戶的ysi.這樣可以抵御SDC冒充用戶的攻擊.同時本方案的共享密鑰發(fā)放是在公開信道上進(jìn)行的.

3）在部分簽名階段，敵手無法偽造部分簽名Eji.因為

且Ki1，δi，xji都是未知的，部分簽名Eji無法確定.

4）少于t個成員無法生成群簽名，滿足門限的性質(zhì).

根據(jù)式（4），如果成員少于t人，那么故群簽名的驗證肯定通不過.

5）敵手得到一個合法的群簽名（E，Ψ，W，M，?i），不可能驗證它，滿足有向簽名的性質(zhì).

因為從YR＝g1xRmod p，TixR＝Δimod p求解xR是一個離散對數(shù)問題.故敵手無法得知xR并驗證

4 結(jié) 論

本文提出了一種新的（t，n）有向門限簽名方案，該方案與以往的一些有向門限簽名方案［2－4］相比具有更高的安全性：1）在文獻(xiàn)［2－4］中，用戶的秘密份額全部由SDC中心產(chǎn)生，因此SDC知道每個用戶所持有的秘密份額，這樣就不能抵抗內(nèi)部人員的攻擊.在本方案中，通過用戶自己選擇一個秘密數(shù)xi解決了內(nèi)部攻擊問題；2）在文獻(xiàn)［2－4］中，秘密共享方式是Shamir門限體制或者Asmuth－Bluoom體制，這種方式下，只要t個人合謀就能恢復(fù)主密鑰，系統(tǒng)也就不具有安全性.在本方案中，改進(jìn)了Shamir門限體制，通過用戶提供的（ui，ysi）和SDC提供的（0，s）合作來確定多項式f（x），從而使得t個人或者更多的人合謀無法求出主密鑰S；3）本方案滿足有向性和門限的性質(zhì)；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］.浙江大學(xué)學(xué)報：理學(xué)版，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］.浙江大學(xué)學(xué)報：理學(xué)版，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規(guī)則”問題［J］.河南師范大學(xué)學(xué)報：自然科學(xué)版，1998，26（3）：88－90.

A New Directed Threshold Signature Scheme

WEN Xiao－h(huán)ua，WANG Xiang－jin，SHEN Zhong－h(huán)ua
（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—），男，副教授，主要從事數(shù)論與密碼學(xué)、信息安全技術(shù)、電子商務(wù)等研究.E－mail：ahtshen＠126.com