密文長度固定的基于身份環簽密方案

摘 要:利用雙線性對技術提出了一種無須隨機預言機的基于身份環簽密方案。密文的大小是一個常量，并且與環的大小無關。通過引入了選擇身份和選擇消息攻擊的安全模型，利用DHI問題的困難性，證明了方案的不可偽造性，同時利用DBDHE問題的困難性，證明了方案在選擇身份和選擇密文攻擊下的不可區分性。與其他的環簽密方案相比，該方案具有較高的效率。

關鍵詞:環簽密; 雙線性對; DBDHE問題; DHI問題

中圖分類號:TP309 文獻標志碼:A

文章編號:1001-3695(2010)03-1022-04

doi:10.3969/j.issn.1001-3695.2010.03.059

Identity-based ring signcryption scheme with constant size ciphertext

SUN Hua， ZHENG Xue-feng， YU Yi-ke， HAN Xiao-guang

(School of Information Engineering， University of Science Technology Beijing， Beijing 100083， China)

Abstract:This paper presented an identity-based ring signcryption scheme without random oracle by using bilinear pairings. The size of the ciphertext was a constant and independent of the size of the ring. By introducing the selective identity and selective chosen message attack model， this paper proved unforgeability of the scheme under the hardness of DHI problem and its indistinguishability against selective identity and chosen ciphertext attack under the hardness of DBDHE problem. This scheme is more efficient compared with other ring signcryption schemes.

Key words:ring signcryption; bilinear pairing; decisional bilinear Diffie-Hellman exponent problem;Diffie-Hellman inversion problem

基于身份的密碼體制由Shamir[1]于1984年首先提出。它消除了傳統PKI體制中對證書的操作，簡化了密鑰管理。Boneh等人[2]提出了第一個實用的基于身份加密方案，隨后一些標準模型下基于身份的加密方案[3~5]和簽名方案[6，7]被相繼提出。

保密和認證是公鑰密碼學的兩項最基本服務。公鑰加密方案旨在提供機密性，而數字簽名提供認證和不可否認性。目前，在許多現實的密碼應用中要求同時達到這兩個屬性。1997年Zheng Yu-liang[8]首次提出了簽密的概念，即能夠在一個操作步驟內完成加密和簽名數據兩項功能，而其計算成本卻低于分別進行簽名和加密的方法。簽密的不足之處在于它增大了最終密文的長度，并且增加了發送者和接收者的計算時間。隨后一些有效的簽密方案被提出，Baek等人[9]提出了第一個在形式化安全模型下可證明安全的簽密方案，文獻[10，11]將基于身份的簽名與加密進行結合從而生成基于身份的簽密方案，然而這些方案僅僅是在隨機預言模型下可證明安全的。

環簽密可使用戶在一潛在的發送用戶群下對消息進行簽密，而不會泄露真實簽密者的身份。因此，環簽密的消息除了具有可認證和機密性外，還具有匿名性。將基于身份的密碼體制與環簽密結合，可以得到基于身份的環簽密方案，它不僅具有環簽密的屬性同時還擁有身份密碼體制的優點。Huang等人[12]首次提出了基于身份的環簽密方案，可是該方案計算低效。Zhang等人[13]提出了可認證的基于身份環簽密方案，實際發送者可以向驗證者證明該簽密確實是由他產生的。Zhu等人[14]提出了另外一種可證安全的基于身份環簽密方案。

目前已有的環簽密方案大多是在隨機預言模型下證明安全的，并且密文的長度隨著環大小的增長而線性增長。因此，設計密文長度固定的標準模型下可證安全的基于身份環簽密方案更具有實際意義。

1 預備知識

1.1 雙線性對

設G、GT是兩個階為素數q的循環群，g是群G的生成元，雙線性對e:G×G→GT是具有如下性質的映射:

a)雙線性。對于所有的P，Q∈G與a，b∈Z，都有e(Pa，Qb)=e(P，Q)ab。

b)非退化性。e(g，g)≠1。

c)可計算性。存在一個有效的算法計算e(P，Q)。其中P，Q∈G。

1.2 困難假設

定義1 給定g，h，T ，gαi∈G，i=1，…，l-1，l+1，…，2l，則DBDHE假設為:判定是否T=e(g，h)αi。

(ε，t，l)-DBDHE假設成立，如果沒有算法至多運行多項式時間t，至少以不可忽略的概率ε解決n-DBDHE問題。

定義2 給定g，gα，gα2，…，gαn∈G，其中α∈

瘙 綄 *P且未知，則n-DHI假設為:計算gαn+1。

(ε，t，n)-DHI假設成立，如果沒有算法至多運行多項式時間t，至少以不可忽略的概率ε解決n-DHI問題。

2 安全模型

2.1 Identity-based ring signcryption(IBRSC)

一個基于身份的環簽密方案由以下四個算法組成:

a)Setup。 給定安全參數k，PKG生成系統公開參數params，公鑰Ppub以及主密鑰msk。

b)Extract。給定身份ID，PKG計算ID的相應私鑰SID，并秘密發送給它。

c)Signcrypt。給定消息m，接收者IDR，發送者IDS的私鑰DS，以及環L={ID1，…，IDn}，該算法生成密文C。

d)Unsigncrypt。該算法輸入密文C，接收者的私鑰DR，環L={ID1，…，IDn}，如果C是一個有效的密文，則生成明文m，否則輸出⊥。

這些算法需滿足基于身份環簽密方案的一致性要求，即如果c=signcrypt(m，L，Ds，IDR)，則m=unsigncrypt(c，L，DR)。

2.2 Indistinguishability

定義3 一個基于身份的環簽密方案在選擇身份選擇密文攻擊下是不可區分的(IND-sID-CCA)。如果沒有概率多項式時間敵手A在下面的游戲中獲得不可忽略的優勢:

敵手A向挑戰者C公開挑戰身份L*。

Setup:挑戰者C運行setup生成系統參數并發送給敵手A，保存msk。

First phase:敵手A可以向挑戰者C發出如下一定數量的詢問:

a)Extract query。A選擇身份ID，C運行extract計算其私鑰DS并發送給A。其中ID不能是環L*中任一成員的身份。

b)Signcrypt query。A選擇簽密者IDS，環L，接收者IDR及明文m。C首先運行extract得到IDS的私鑰DS，然后運行signcrypt生成密文C并發送給A，其中A不能對m*和l*進行簽密詢問。

c)Unsigncrypt query。A選擇環L，接收者IDR和密文C。C首先運行extract得到IDR的私鑰DR，然后運行unsigncrypt。如果C是一個有效的密文，則返回m;否則，返回⊥。

Challenge:A任選兩個長度相同的消息m0，m1，環L*以及挑戰身份IDR，并發送給C。A必須在第一階段中沒有詢問IDR的私鑰。C任選一位b∈{0，1}，計算簽密C*，并將其發送給A。

Second phase:A可以如第一階段那樣發起一定數量的詢問，但不能詢問IDR的私鑰，且不能對C*發起解密詢問。

Guess: 最后，A輸出一位b'。如果b=b'，那么A贏得游戲。定義敵手A獲得成功的優勢為AdvIND-sID-CCAA=|Pr[b=b']-1/2|。

2.3 Existential unforgeability

定義4 一個基于身份的環簽密方案在選擇身份選擇消息攻擊下可抵抗存在性偽造(EUF-sID-CMA)。如果沒有概率多項式時間敵手A在下面的游戲中獲得不可忽略的優勢:

敵手A向挑戰者C公開挑戰身份L*和挑戰消息m*。

Setup: 挑戰者C運行setup生成系統參數params并發送給敵手A，保存msk。

Query:A可以像定義3中的第一階段那樣，發起一定數量的詢問。

Forgery:A輸出元組(L*，IDR，C*)，其中環L*中任一成員及IDR的私鑰沒有被詢問。如果unsigncrypt(L*，DR，C*)的結果不為⊥，那么A贏得游戲。

3 密文長度固定的基于身份環簽密方案

3.1 方案描述

設兩個無碰撞哈希函數H1:{0，1}*→

瘙 綄 *p和H2:{0，1}*→

瘙 綄 *p可將任意長度的身份ID和消息m映射為兩個非零整數，方案構成如下:

Setup:選取e:G×G→GT，G的階為P，g為其生成元。隨機選取α∈

瘙 綄 p，g2∈G并計算g1=gα。選取u'∈RG，向量U^=(1，2，…，n，)∈Gn。則系統公開參數為params=(G，GT，e，g，g1，g2，u'，)，主密鑰為msk=gα2。

Extract:對于身份ID，令id=H1(ID)，任選ri∈

瘙 綄 *p，1≤i≤n+1，計算身份ID的私鑰為dID=(gα2(u'idi)ri，gri，ri1，…，rii-1，rii+1，…，rin)=(a0，b0，c1，…，ci-1，ci+1，…，cn)。

Signcrypt:令L={ID1，…，ID′n}為包括實際簽密者IDk在內的環L中n′個成員的集合，idi=H1(IDi) ，1≤i≤n，m為待簽密消息，m=H2(m，L)。設簽密接收者的身份為IDr，idr=H1(IDr)，簽密者的私鑰為dIDk。簽密者隨機選取t∈

瘙 綄 p，計算C1=gt，C2=ak，0(∏n′j=1，j≠kcidjk，j)cmk，n′+1(u'id11…idn'n'mn'+1)t，C3=bk，0gt，C4=(u'idrr)t，C5=e(g1，g2，)t〈m，IDk，C2，C3〉則生成的簽密為c=(C1，C2，C3，C4，C5)。

Unsigncrypt:接收者IDr收到簽密c后，進行如下計算:

a)接收者IDr用其私鑰dIDr=(ar，0，br，0，cr，1，…，cr，i-1，cr，i+1，…，cr，n)計算W=e(C1，ar，0)#8226;e(C4，br，0)-1。

b)由〈m，IDk，C2，C3〉=C5W，環成員組L={ID1，…，IDn}，計算m=H2(m，L)，當等式e(g，C2)=e(g1，g2)#8226;e(C3，u'id11…idn'n'mn'+1)成立時，c為一個有效的環簽密。

3.2 方案正確性

方案的正確性可以由下面的等式進行驗證:

由dIDr=(ar，0，br，0，cr，1，…，cr，i-1，cr，i+1，…，cr，n)可得:W=e(C1，ar，0)#8226;e(C4，br，0)-1=e(gt，gα2(u'idrr)rr)#8226;e(grr，(u'idrr)t)-1=e(gt，gα2)#8226;e(gt，(u'idrr)rr)e(grr，(u'idrr)t)=e(g2，g1)t

對c進行驗證可得:

e(g，C2)=e(g，ak，0(∏nj=1，j≠kcidjk，j)cmk，n′+1(u′id11…idn′n′mn′+1)t)=e(g，gα2(u′id1…idn′n′mn′+1)rk+t)=e(g1，g2)e(C3，u′id11…idn′n′mn′+1)

3.3 方案安全性

定理1 假定(ε′，t′，n)-DHI成立，本文的方案在選擇身份攻擊模型下是(ε，t，qe，qs，qu)-不可偽造的，即如果存在運行時間至多為t、優勢為ε的敵手A，且其私鑰詢問的次數最多為qe，簽密詢問最多為qs，解密詢問最多為qu，那么可以概率ε′≥ε(1-1p)qe(1-1p2)qs解決DHI問題，其時間為t′=t+o((qe+3qs+2qu)nρ)+o((qe+3qs+2qu)nτ)+5τ′，ρ和τ分別為G中一次乘法運算和指數運算的時間，τ'為一次雙線性對運算的時間。

證明 假定存在(ε，t，qe，qs，qu)-敵手A，那么能夠構造算法B，它可以利用A以概率ε′時間t′解決DHI問題。

給定B一個DHI問題的實例(g，gα，…，gan)，為了計算gαn+1，B模仿A的挑戰者，其過程如下:

敵手A將挑戰身份L*={ID*1，…，ID*n-1}和挑戰消息m*發送給B。

Setup:令id*i=H1(ID*i)，1≤i≤n-1，id*n=H2(m*，L*)。為了產生系統參數，B首先選擇γ∈R

瘙 綄 p，設g1=gα，g2=gan，gγ+αn。其次，B選擇γ1，…，γn∈R

瘙 綄 p，并令i=gγi/gan-i+1，1≤i≤n。最后，B選擇γ∈R

瘙 綄 p，并令u′=gδ#8226;∏ni=1gαn-i+1id*i。B將公開參數params=(g，g1，g2，u′，1…，n)發送給A，相應的主密鑰為gα2=gα(γ+αn)。

可以看出這些參數的分布與一個真正的挑戰者所產生的公開參數是一樣的。

Queries:B將按如下方式模仿A對挑戰者發起的詢問:

a)Extract query。當詢問身份ID的私鑰時，B計算id=H1(ID)，如果id=H1(ID*i)，1≤i≤n-1，那么B將失敗退出。否則，B任選∈

瘙 綄 p并令r=α(id-id*1)+，構造其私鑰dID=(gα2(u′id1)r，gr，r1，…，ri-1，ri+1，…，rn)。

a0=gα(γ+αn)gδ+∑nj=1αn-j+1id*j#8226;(gγ1-αn)idr=gαγ#8226;gδ+γ1id#8226;g∑nj=2αn-j+1id*jr#8226;gαn(id*1-id) b0=gr=gα(id-id*1)+ ck=rk=g(γk-αn-k+1)α(id-id*1)+，2≤k≤n

為了描述方便，計算中選擇了id*1，當選擇其他id*i(2≤i≤n-1)時，計算過程是相同的。

b)Signcrypt query。敵手A可以任意發起在環L={ID1，…，IDn′}和接收者IDr下對消息m的簽密詢問。令idi=H1(IDi)，1≤i≤n，idn′+1=H2(m，L)。如果{id1，…，idn′+1}與{id*i，…，id*n}相同或是其前綴，那么B將失敗退出。否則存在k≤n，滿足idk≠id*k。為了響應A發出的簽密詢問，本文選取序號最小的k，如同私鑰詢問中那樣生成idk的私鑰，然后運行signcrypt算法生成一個有效的簽密c并發送給A。

c)Unsigncrypt query。敵手A可以任意發起在環L和接收者IDr下對密文c的解密詢問。如同私鑰詢問中那樣，B首先計算IDr的私鑰，然后運行unsigncrypt算法。如果c是一個有效的密文，則返回m;否則，返回⊥。

Forgery:最后，A輸出在環L*和消息m*下的環簽密c*，其中L*和m*是在游戲開始時由A選定的。令c*=(c*1，c*2，c*3，c*4，c*5)，C*3=g，可得:

C*2=gα2(u'∏ni=1id*ii)=gα2gδ+∑nj=1αn-j+1id*j#8226;(∏ni=1gγi-αn-i+1)id*i=gα2(gδ+∑nj=1γiid*i)gαn+1=gα2/gαγ=C*2/C*δ+∑nj=1γiid*i3gγ1

這就是DHI問題實例的解。

下面分析算法B成功的概率。

為使整個模擬過程沒有失敗退出，需滿足兩個條件:

a)對身份ID進行私鑰詢問時，需滿足id=H1(ID)，id≠H1(ID*1)。

b)對環L={ID1，…，IDn′}進行簽密時，{id1，…，idn'+1}必須不與{id*1，…，id*n}相同或不為其前綴。

本文定義事件Ai，Bj如下:

Ai:H1(IDi)≠H1(ID*1)，i=1，…，qe。ID*1是在前面的描述過程中選定的，這里需與前面相同。

Bl:{idl，1，…，idl，n'l+1}≠{id*1，…，id*}，l=1，…，qs，2≤≤n。

那么B不失敗退出的概率為

Pr[

瘙 綈 abort]≥Pr(Λqei=1Ai)Λ(Λqsl=1Bl)

其中:事件Ai和Bl是相互獨立的。由

Pr[Ai]=1-1/p，Pr[Bl]=1-(1/p)n′l+1

可得:Pr[

瘙 綈 abort]≥Pr(Λqei=1Ai)Λ(Λqsl=1Bl)=(1-1p)qe∏qsl=1(1-(1p)n′l+1)≥(1-1p)qe(1-1p2)qs。

如果整個模擬過程中B沒有失敗退出，A可以概率ε生成一個有效的偽造環簽密，那么B能以概率ε'≥ε(1-1p)qe(1-1p2)qs解決DHI問題的實例。

時間復雜度分析:私鑰詢問需要O(n)次G中乘法運算和O(n)次指數運算，簽密詢問需要O(3n)次G中乘法運算、O(3n)次指數運算以及O(1)次雙線性對運算， 解密詢問需要O(2n)次G中乘法運算、O(2n)次指數運算以及O(4)次雙線性對運算，故B總的運行時間為

t′=t+O((qe+3qs+2qu)nρ)+O((qe+3qs+2qu)nτ)+5τ′

定理2 在DBDHE困難問題的假設下，本文的方案是IND-sID-CCA安全的。

證明 假設敵手A能以不可忽略的優勢攻擊本方案，則能夠構造算法B，B可以利用A解決DBDHE問題。

給定B一個DBDHE問題的實例(g，h，gα…，gαl，gαl+2…，gα2l，T)，其目標是判斷是否有T=e(g，h)αl+1。B模仿A的挑戰者，其過程如下:

敵手A將挑戰身份L*={ID*1，…，ID*n-1}發送給B。

Setup:用前面證明中相同的方法構造系統公開參數，并發送給A。

Phase 1:如同前面的證明那樣，A可以發起一定數量的私鑰詢問、簽密詢問及解密詢問。

Challenge:一旦A確定第一階段結束，輸出L*，兩個長度相同的消息m0、m1以及簽密接收者IDr。如果A在第一階段詢問了L*中任一成員或IDr的私鑰，那么B將失敗退出。B任選一環簽密者IDk，使用前面證明中相同的方法構造其私鑰dIDk。B任選一位b∈{0，1}，c∈R

瘙 綄 p，并計算id*n=H2(mb，L)。令C1=h=gc，c2=ak，0(∏n′j=1，j≠kcidjk，j)cmk，n′+1(u′id11…idn′n′mn′+1)c，C3=bk，0gc，C4=(u'id*rr)c，C5=T#8226;e(g1，h)γ〈mb，IDk，C2，C3〉。

如果T=e(g，h)αl+1，可得:e(g，h)αl+1#8226;e(g1，h)γ=e(g1，hα1+γ)=e(g1，g2)c因此，C5=e(g1，g2)c〈mb，IDk，C2，C3〉。

可知CT=(C1，C2，C3，C4，C5)是在挑戰身份L*下對mb的一個有效環簽密。

Phase 2:敵手A可如同階段1那樣，發出一定數量的私鑰詢問、環簽密詢問及解密詢問，但是A不能進行IDr的私鑰詢問及CT的解密詢問。

Guess:最后，A輸出對b的猜測b′。如果b=b′，則B輸出1，表示T=e(g，h)αl+1;否則，B輸出0，表示T是GT中一隨機元素。因此，如果存在一個敵手以不可忽略的概率進行CCA攻擊，那么就存在一個算法可以不可忽略的概率解決DBDHE問題，而這與DBDHE是一個困難問題相矛盾，故方案是IND-sID-CCA安全的。

3.4 方案效率

由于雙線性對計算所花費的計算成本遠高于元素的點乘運算和指數運算，只考慮雙線性對的計算成本。文獻[12，14]的簽密和解密階段所需的雙線性對計算分別為n+2和3及1和2，密文長度分別為2n+3及n+4。在本方案中，簽密和解密階段分別需要計算1和2次，而密文長度為5，因此方案具有較高的效率。

4 結束語

本文提出了一個密文長度固定的基于身份環簽密方案。方案中無須借助隨機預言機，在標準模型下可證明它是安全的。與現有的環簽密方案相比，本方案中密文的長度固定，不隨環的線性增長而增長，具有較高的效率。利用DBDHE問題和DHI問題的困難性，分別對方案的不可區分性和不可偽造性進行了安全性證明，并進行了相應的概率分析和時間復雜度分析。

參考文獻:

[1]SHAMIR A. Identity-based cryptosystems and signature schemes[C]//Proc of CRYPTO 1984.New York: Springer-Verlag， 1985: 47-53.

[2]BONEH D，FRANKLIN M. Identity-based encryption from the Weil pairin[C]//Proc of CRYPTO.Berlin:Springer， 2001:213-229.

[3]BONEH D，BOYEN X. Efficient selective-id secure identity based encryption without random oracles[C]//Proc of EUROCRYPT.Berlin: Springer-Verlag， 2004: 223-238.

[4]BONEH D，BOYEN X. Secure identity based encryption without random oracles[C]//Proc of CRYPTO.Berlin: Springer-Verlag， 2004: 443-459.

[5]GENTRY C. Practical identity-based encryption without random oracles[C]//Proc of EUROCRYPT. Berlin:Springer-Verlag， 2006: 445-464.

[6]PATERSON K G，SCHULDT J C N. Efficient identity-based signatures secure in the standard model[C]//Proc of ACISP. Berlin:Springer-Verlag，2006:207-222.

[7]REN Yan-li ，GU Da-wu . Efficient hierarchical identity based signature scheme in the standard model[J]. Wuhan University Journal of Natural Sciences，2008，13(6): 665-669.

[8]ZHENG Yu-liang. Digital signcryption or how to achieve cost(signature encryption)<

[9]BAEK J，STEINFLD R， ZHENG Yu-liang . Formal proofs for the security of signcryption[C]//Proc of PKC.London: Springer-Verlag， 2002: 363-366.

[10]MALONE-LEE J. Identity-based signcryption[J/OL].(2002).[2009-06-15]. http://eprint.iacr.org/.

[11]LIBERT B，QUISQUATER J J. New identity based signcryption schemes from pairings[EB/OL].(2003).[2009-06-15]. http://eprint.iacr.org/.

[12]HUANG Xin-yi ， SUSILO W， MU Yi， et al. Identity-based ring signcryption schemes: cryptographic primitives for preserving privacy and authenticity in the ubiquitous world[C]//Proc of Advanced Information Networking and Application. 2005:649-654.

[13]ZHANG Ming-wu ， YANG Bo ， ZHU Shen-lin， et al. Efficient secret authenticatable anonymous signcryption scheme with identity privacy[C]//Proc of PAISI. Berlin:Springer-Verlag， 2008: 126-137.

[14]ZHU Zhen-chao， ZHANG Yu-qing， WANG Feng-jiao. An efficient and provable secure identity-based ring signcryption scheme[EB/OL].[2009-06-15].http://dx.doi.org/10.1016/j.csi.