程小剛，杜吉祥

（1.華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建 泉州362021；2.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京210016）

0 引 言

K次條件群簽名［1］是對(duì)傳統(tǒng)群簽名［2］的擴(kuò)展，加上了次數(shù)限制，即只要簽名的次數(shù)小于K，那么生成的簽名是不可追蹤的 （類似于環(huán)簽名［3－4］），而當(dāng)簽名的次數(shù)大于K時(shí)，其生成的簽名是可追蹤的 （類似于群簽名）。

本文考慮如下的進(jìn)一步擴(kuò)展的情形：K＋L次條件群簽名，即小于K次簽名是不可追蹤的，K次之后的L次簽名是可由群管理員 （GM）追蹤的，再之后其生成的簽名身份是公開的 （即任何人可追蹤）。K＋L次條件群簽名在簽名次數(shù)小于K是可認(rèn)為是類似環(huán)簽名 （匿名且不可追蹤），大于K小于K＋L時(shí)是群簽名 （匿名但GM可追蹤），大于K＋L是普通簽名 （任何人可追蹤）。

考慮如下應(yīng)用場(chǎng)景：電子貨幣應(yīng)用中，比如用簽名作為貨幣，商家接收簽名作為貨幣，只要簽名驗(yàn)證通過就接收下來并提供商品或服務(wù)，然后商家向銀行發(fā)送簽名進(jìn)行存款操作，此時(shí)銀行根據(jù)此前所有接收的簽名進(jìn)行比較（相同的當(dāng)然不能再接收）與追蹤，只要此用戶所做的簽名次數(shù)不超過K次，那么追蹤不到 （保證了用戶的隱私性），要是超過K次，那么銀行就能追蹤到了并可以予以處罰，可見K在此可作為銀行發(fā)給用戶的電子貨幣的面值來使用；如果用戶繼續(xù)濫用其電子貨幣并超過了K＋L次，那么他的身份就公開可追蹤了，即不僅銀行，連公眾也能找出他的真實(shí)身份了。

K次條件群簽名構(gòu)建的思想大致如下，GM （如銀行）公布一個(gè)列表有K個(gè)隨機(jī)值，用戶在生成群簽名時(shí)每次用其中的一個(gè)，只要用戶的簽名次數(shù)不超過K個(gè)，那么他的身份就是隱匿的，若超過K次，那么他就必須重復(fù)使用這K個(gè)隨機(jī)值中的一個(gè)，那么他的身份信息就暴光了；對(duì)于K＋L次條件群簽名的構(gòu)建，也有一個(gè)K＋L隨機(jī)值的列表，前面K個(gè)值是隨機(jī)的且相互獨(dú)立 （用戶用它進(jìn)行簽名就是匿名的），而后面的L個(gè)隨機(jī)值同前面的值是有秘密關(guān)系的 （比如離散對(duì)數(shù)），這個(gè)秘密信息由GM保存，這樣只要用戶做了超過K次，而小于K＋L次的群簽名，GM就可以進(jìn)行追蹤 （外人沒有此秘密信息，仍然不能追蹤），而當(dāng)用戶做了大于K＋L次的群簽名，他必須重用列表中的某個(gè)值，此時(shí)任何人都可以進(jìn)行追蹤了。

對(duì)于結(jié)合群簽名與環(huán)簽名特性已有了一些相關(guān)的工作，“可撤銷環(huán)簽名”［5］是在環(huán)簽名的基礎(chǔ)之上加入了追蹤的功能 （并能自主選擇能進(jìn)行追蹤的群體）；“條件環(huán)簽名”［6］是在環(huán)簽名中加入如下功能：簽名者可通過一確認(rèn)協(xié)議來證明某環(huán)簽名是自己簽的，而非簽名者能否認(rèn)不是自己發(fā)出的簽名；“可追蹤環(huán)簽名”［7］中簽名是不可追蹤的，但如果對(duì)同一消息簽了兩次名 （如投了兩次票），那么就可追蹤其身份了；也有一些方案對(duì)環(huán)簽名加入了追蹤功能［8－9］；DAA（direct anonymous attestation）是群簽名的一種變體［10］，群成員在簽名是可自己控制匿名的程度 （即可控制兩個(gè)群簽名之間是否可鏈接）。

1 數(shù)學(xué)假設(shè)

本文用到了基于雙線性群的一些數(shù)學(xué)假設(shè)，所以先給出雙線性群的定義：

雙線性群：設(shè)G和GT是階為大素?cái)?shù)q的群，并具有滿足下列條件的映射e：G×G→GT：

（1）雙線性性：對(duì)任意的a，b∈Zp，有e（aP，bP）＝e（P，P）ab；

（2）非退化性：對(duì)任意的生成元g，h∈G，有e（g，h）是GT的生成元；

（3）有效性：存在高效的算法能生成具有映射e的群G和GT，且有高效算法對(duì)任意的g，h∈G計(jì)算e（g，h）。

d－BDH （decisional Bilinear Diffie－Hellman）假 設(shè)：對(duì)任意的多項(xiàng)式時(shí)間敵手A，下列事件發(fā)生的概率是可忽略的 ｜Pr［A（aP，bP，cP，e（P，P）abc）＝ 1］－Pr［A（aP，bP，cP，T）＝1］｜，其中T是GT中的隨機(jī)元素。

q－SDH （strong diffie－Hellman）假設(shè)：對(duì)任意的多項(xiàng)式時(shí)間敵手A，下列事件發(fā)生的概率是可忽略的：Pr［A（P，xP，x2P，…，xqP），其中c是任意隨機(jī)數(shù)。

GT中的DDH （decisional diffie－Hellman）假設(shè)：對(duì)任意的多項(xiàng)式時(shí)間敵手A，下列事件發(fā)生的概率是可忽略的 ｜Pr［A（T，Ta，Tb，Tab）＝ 1］－ Pr［A（T，Ta，Tb，Tc）＝1］｜，其中T是是GT中的隨機(jī)元素。

注意在此強(qiáng)調(diào)是GT中的DDH假設(shè)，因?yàn)橛捎陔p線性映射e的存在，在G中的DDH問題是容易解決的。

2 K＋L次條件群簽名的定義與安全性需求

定義1 K＋L次條件群簽名由下面6個(gè)算法構(gòu)成：

（1）Setup：由 GM 生成公開參數(shù)，群公私鑰 GPK和GSK；

（2）Join：用戶可加入群中成為成員，獲得GM頒發(fā)的成員證書，可用于生成簽名；

（3）Sign：用戶利用獲得的成員證書可生成簽名 （只要他簽名的次數(shù)小于K，其身份是隱匿的，GM也不能追蹤到）；

（4）Verify：任何人有群公鑰都可驗(yàn)證某一簽名是否合法 （即確信此簽名由群中某人簽發(fā)）；

（5）GM Trace：當(dāng)其簽名的次數(shù)大于K次且小于等于K＋L時(shí)，只有GM可用GM Trace算法對(duì)其進(jìn)行追蹤

（6）Public Trace：若某成員簽名的次數(shù)超過了K＋L次，那么任何人可追蹤出其真實(shí)的身份。

K＋L次條件群簽名安全性需求如下：

正確性：要求一個(gè)誠實(shí)的用戶加入群中成為群成員之后，可以生成簽名并驗(yàn)證通過；

K－完全匿名性：誠實(shí)用戶只要其簽名的次數(shù)是小于等于K的，那么他的身份是完全隱匿的；

K＋1－GM可追蹤性：某用戶簽名的次數(shù)超過K次以上，且小于等于K＋L次的，那么GM可追蹤出他的身份；

K＋L＋1－公開可追蹤性：某用戶簽名的次數(shù)超過K＋L次以上的，那么任何人可追蹤他的身份；

不可偽造性：群外任何人不能生成合法驗(yàn)證通過的簽名；

防陷害性：任何人 （包括GM）都不能冒充某成員生成合法的簽名。

3 方案構(gòu)建

基于［1］中的K－TAA方案，構(gòu)建K＋L次條件群簽名如下：

經(jīng)由上述分析可以得知，實(shí)施高質(zhì)量的改種果樹造林作業(yè)設(shè)計(jì)十分具有必要性，不僅有助于為廣大農(nóng)民提供更多的就業(yè)機(jī)會(huì)，促使其可以經(jīng)由勞務(wù)投入的方式獲取收入，也有利于帶動(dòng)農(nóng)村經(jīng)濟(jì)發(fā)展，推進(jìn)社會(huì)主義新農(nóng)村的建設(shè)進(jìn)程，同時(shí)，在林地成林以后，相應(yīng)區(qū)域土地的保肥保水能力也會(huì)大幅度提升，對(duì)后期各種作物更好的生長(zhǎng)和發(fā)育具有積極意義，有助于獲取到更多的經(jīng)濟(jì)效益。

Setup：GM選具有雙線性映射的階為素?cái)?shù)p的群G和GT，e：G×G →GT滿足e（aP，bP）＝e（P，P）ab，選P，P0，H←G，γ←Z＊P，群公鑰GPK＝（P，Ppub，P0，H，Δ）；群私鑰GSK＝γ；而且Ppub＝γP，Δ＝e（P，P）；并創(chuàng)建兩個(gè)列表，List1有K＋L個(gè)隨機(jī)元素對(duì) （Θi，＾Θi）∈G×GT，前面K個(gè)都是相互獨(dú)立的隨機(jī)元素對(duì)，后面L個(gè)同前面的元素對(duì)有秘密關(guān)系 （即離散對(duì)數(shù)），GM掌握此秘密關(guān)系用于追蹤 （見下 GM Trace），List2是 （i，β），i表示用戶身份，β＝Δx，x是用戶私鑰；GM保存所有簽名至一列表中 （如商家把用戶的簽名發(fā)給銀行進(jìn)行存款操作），且此列表是公眾可訪問的。

Join：此時(shí)用戶和GM之間執(zhí)行的一交互協(xié)議，完成后用戶 獲得成員 公 鑰 mpk ＝ （a，S，C，β），而且用戶 私 鑰msk＝x，滿足關(guān)系C＝xP，β＝Δx，協(xié)議如下：

（1）用戶Ui選擇隨機(jī)的x’，r←，并把對(duì)x’的承諾C’＝x’P＋rH傳給GM；

（3）Ui計(jì)算x＝y(tǒng)＋x’y’及 （C，β）＝（xP，Δx），再把 （i，β）加到List2中去，然后Ui將 （C，β）傳給GM，并附上一標(biāo)準(zhǔn)的證明 PK｛（x，r′）：C ＝xP ∧yP ＋y′C′－C ＝r′H｝此PK表明C是正確地由C’，y，y’計(jì)算出來的，而且Ui知道x滿足C＝xP；

（4）GM 驗(yàn)證 （i，β）存在于List2中，β＝e（C，P）且所附的證明是合法的。接著GM選取一隨機(jī)的（此a要同以前GM頒發(fā)過的證書中的任一a都不同），計(jì)算S＝），并把 （S，a）傳給 U；i

（5）Ui驗(yàn)證等式e（S，aP＋Ppub）＝e（C＋P0，P）是否成立，是的話則此Ui成為新成員，他的用戶私鑰msk＝x，他的公鑰mpk＝ （a，S，C，β）。

Sign：第i次簽名用 List1中的 （Θi，＾Θi），利用一CRH（collision resistant hash）函數(shù)H將第i個(gè)消息映射成Z＊p中的元素li，計(jì)算 （Γ，＾Γ）＝ （Θx，（Δl＾Θ）x），再生成PK｛（a，S，x）：（Γ，＾Γ）＝ （Θx，（ΔlΘ）x）∧e（S，aP＋Ppub）＝e（xP＋P0，P）｝，此表示一基于ROM模型的非交互零知識(shí)證明用戶有秘密的 （a，S，x）滿足后面的方程式，方程式中其他值都是已知的，構(gòu)建方法如下：

（2）計(jì)算

注意在此把Hash函數(shù)H看成一隨機(jī)語言器 （random oracle）；

（3）在ZP中計(jì)算s0＝k0＋cr3，s1＝k1＋cr1r2r4a，s2＝k2＋cr1r2r4，s3＝k3＋cr1r2r4x；

（4）輸出簽名為 （X，U1，U2，U3，c，s0，s1，s2，s3）；

Verify：檢查等式e（U3，U1）＝？e（X，P）是否成立；再令T1’＝s1P＋s2Ppub＋s0H－cU2，T2’＝s3P＋s2P0－cX，Π1′＝ Θs3Γ－s2，Π2′＝＾Θs3＾Γ－s2，檢查是否有：

T2′ Π1′ Π2′）都成立的話接受簽名，否則拒絕；

Public trace：為介紹簡(jiǎn)單起見我們先看Public Trace是怎么做的，用戶做了K＋L次以上的簽名，他必然重用了List1中的某個(gè)元素對(duì) （因元素對(duì)只有K＋L個(gè)），則這兩個(gè)簽名的Γ 值是一樣的，我們可以計(jì)算β，就可從List2中找到對(duì)應(yīng)的用戶i了；

4 安全性與效率

定理1基于d－BDH、q－SDH和GT中的DDH假設(shè)，及ROM模型，上述K＋L次條件群簽名方案滿足正確性、K－完全匿名性、K＋1－GM可追蹤性、K＋L＋1－公開可追蹤性、不可偽造性和防陷害性。

證明：（1）正確性：顯然由方案的算法可見，誠實(shí)用戶生成的簽名能通過驗(yàn)證；

（2）K－完全匿名性：用戶的簽名由 （Γ，＾Γ，PK）構(gòu)成，由PK的零知識(shí)特性可知PK部分不會(huì)泄露用戶的任何身份信息，而Γ＝Θx，＾Γ＝＾Θx部分的確包含用戶的身份秘密信息x，但基于d－BDH假設(shè)和群GT中的DDH假設(shè)，找出用戶的真實(shí)身份計(jì)算上是不可行的：判斷Γ＝Θx與List2中的β＝Δx是否為同一個(gè)x，是一個(gè)d－BDH難題；而判斷＾Γ＝＾Θx與β＝Δx是否為同一個(gè)x，是一個(gè)GT群中的DDH難題；

在此我們指出由于雙線性映射e，在群G中DDH問題是可解的，因而同一用戶做的簽名雖然是匿名的，但是可鏈接的，為克服這一問題，可采用 “非對(duì)稱”的雙線性映射e：G1×G2→GT，其中G1和G2是不同的群，而且DDH假設(shè)在G1、G2中都成立；

（3）K＋1－GM可追蹤性：用戶做了K次以上的簽名后，必然用了List1中后面L個(gè)隨機(jī)元素對(duì)中的一個(gè)，而這些元素對(duì)同前面的元素對(duì)是有秘密關(guān)系的如ΘK＋1＝Θr1，＾ΘK＋1＝ ＾Θr1， 且 GM 知 道 此 秘 密 的 r， 那 么 ＾ΓK＋1＝（ΔlK＋1＾ΘK＋1）x，＾Γ1＝ （Δl1＾Θ1）x，則：

GM通過嘗試List2中的每一個(gè)β是否滿足上式即可找出簽名者；

（4）K＋L＋1－公開可追蹤性：用戶做了K＋L次以上的簽名，必然重用了List1中元素對(duì)中的某一個(gè)，則這兩個(gè)簽名的Γ值是一樣的，而＾Γ值是不一樣的 （因用的l值不一樣），則可計(jì)算Δx＝β，解出β，從而可在List2中找出實(shí)際簽名者；

（5）不可偽造性：方案中的用戶證書中的S實(shí)際上是GM對(duì)a的BB簽名，那么由BB簽名［11］的安全特性，在q－SDH假設(shè)之下，GM之外的任何人都不能生成這樣的 （S，a）簽名／消息對(duì)，即任何群外的人都不能生成合法的簽名；

（6）防陷害性：在用戶加入群時(shí)，與GM執(zhí)行交互協(xié)議后，GM得到C，用戶的到私鑰x滿足C＝xP，注意GM是不知道此x的 （由離散對(duì)數(shù)假設(shè)，GM也計(jì)算不出此秘密），那么GM就不能冒充此用戶進(jìn)行簽名操作，其他人當(dāng)然也不能冒充此用戶進(jìn)行簽名操作。

由上述構(gòu)建可見，簽名與驗(yàn)證的計(jì)算量都是常數(shù)級(jí)的O（1），比較高效；Public Trace的計(jì)算量也不大，假設(shè)所有的簽名已排好序，則通過二分查找，可在O（logM）時(shí)間里找到重復(fù)的Γ值 （M為到當(dāng)前為止所有的簽名數(shù)量）；找到后可計(jì)算出β，在List2中找出對(duì)應(yīng)的用戶i也只需要O（logN）工作量 （N為用戶數(shù)量），所以Public Trace的效率為O（logM＋logN）；但GM Trace的工作量較大，分析如下：GM收到一用List1中K＋1項(xiàng)的簽名后，要找出此用戶，必須對(duì)前面的每一個(gè)簽名中Γi的計(jì)算其r次方，判斷是否與當(dāng)前的Γ值相同，顯然工作量為O （M）；找到后可計(jì)算出＾Γri／＾Γ ，再對(duì)List2中的每一個(gè)β計(jì)算βlir－l，看其是否與＾Γri／＾Γ相等來找出到底是哪個(gè)用戶作的簽名，此舉顯然工作量為O（N），所以GM Trace的工作量為O（M＋N），效率相對(duì)較低。

5 結(jié)束語

本文提出了一種新的K＋L次條件群簽名的概念，擴(kuò)展了原有的K次匿名認(rèn)證的概念，可適用于范圍更廣的應(yīng)用場(chǎng)合；給出了其定義與安全性需求，并基于d－BDH、q－SDH假設(shè)給出了一個(gè)具體方案的構(gòu)建；不足之處在于方案的安全性基于ROM模型、GM追蹤的效率不高，下一步工作是研究如何提高效率，及在標(biāo)準(zhǔn)模型下構(gòu)建安全的K＋L次條件群簽名。另外，考慮對(duì)其他或更一般的條件 （如限制可簽署的支票金額等），如何構(gòu)建條件群簽名方案，也是值得研究的課題。

［1］Teranishi I，F(xiàn)urukawa J，Sako K.K－times anonymous authentication［J］.IEICE Transactions on Fundamentals of Electronics，Communications and Computer Sciences，2009，92－A（1）：147－165.

［2］MA Haiying，WANG Zhanjun.Full anonymous dynamic short group signature scheme［J］.Computer Engineering and Design，2010 （6）：1222－1225（in Chinese）. ［馬海英，王占君.完全匿名的動(dòng)態(tài)短群簽名方案 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010（6）：1222－1225.］

［3］WANG Huaqun，JIANG Guoxing，ZHAO Shuping.Efficient ring signature scheme from bilinear pairings［J］.Computer Engineering and Design，2008，29 （6）：1459－1461 （in Chinese）.［王化群，姜國興，趙樹平.高效的基于雙線性對(duì)的環(huán)簽名方案 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29 （6）：1459－1461.］

［4］GE Aijun，MA Chuangui，ZHANG Zhenfeng，et al.Identitybased ring signature scheme with constant size signatures in the standard model［J］.Chinese Journal of Computers，2012，35（9）：1874－1880 （in Chinese）.［葛愛軍，馬傳貴，張振峰，等.標(biāo)準(zhǔn)模型下固定長(zhǎng)度的基于身份環(huán)簽名方案 ［J］.計(jì)算機(jī)學(xué)報(bào)，2012，35 （9）：1874－1880.］

［5］LIU D Y W，LIU J K，MU Y，et al.Revocable ring signature［J］.Journal of Computer Science and Technology，2007，22（6）：785－794.

［6］ZENG S.An efficient conditionally anonymous ring signature in the random oracle model ［J］.Theoretical Computer Science，2012，461 （23）：106－114.

［7］Fujisaki E，Suzuki K.Traceable ring signature ［G］.LNCS 4450：Proceedings of Public Key Cryptography－PKC，Heidelberg：Springer，2007：181－200.

［8］SUN Qingying，WU Keli，XU Huiyan.Signer－traceable ring signcryption scheme ［J］.Computer Enginee－ring，2011，37（16）：129－131（in Chinese）. ［孫慶英，吳克力，徐會(huì)艷.一種可追蹤簽名者的環(huán)簽密方案 ［J］.計(jì)算機(jī)工程，2011，37（16）：129－131.］

［9］HUANG Dawei，YANG Xiaoyuan，CHEN Haibin.Ring signature scheme with revocable anonymity［J］.Computer Engineering and Applications，2010，46 （24）：88－89 （in Chinese）.［黃大威，楊曉元，陳海濱.一種可撤銷匿名性的環(huán)簽名方案［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46 （24）：88－89.］

［10］SONG Yang，LI Lixin，ZHOU Yanzhou，et al.Security analysis and improvement of DAA protocol［J］.Computer Engineering and Design，2010 （1）：26－29 （in Chinese）. ［宋揚(yáng)，李立新，周雁舟，等.DAA協(xié)議的安全性分析及改進(jìn) ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010 （1）：26－29.］

［11］JAO D，Yoshida K.Boneh－boyen signatures and the strong diffie－h(huán)ellman problem ［G］.LNCS 5671：Pairing－Based Cryptography－Pairing，2009：1－16.