標準模型下一種高效的基于身份的多簽密方案

吳振國，祁正華，王 翔

(南京郵電大學 計算機學院，江蘇 南京 210003)

0 引 言

在傳統的基于證書的公鑰密碼系統中，用戶的公鑰和該用戶之間的對應關系通常是由認證中心頒發的證書來綁定的，這種方式會帶來復雜的證書管理問題，也就是說用戶需要對證書的正確性進行驗證，并且存儲大量的證書。1984年Shamir[1]提出了基于身份的公鑰密碼體制，它的基本思想是指由用戶的特征信息，如姓名、ID、電話或者其他已知具有用戶特征的標識符作為該用戶的公鑰，使用這種方法不僅解決了基于證書的公鑰密碼體制中存在的信任問題，而且簡化了它的密鑰管理程序。Zheng[2]于1997年提出了簽密這一新概念，所謂簽密就是指將加密和簽名合二為一，把消息的保密性和認證性集中在一個邏輯步驟內實現，相比于將兩者組合使用的方法具有更高的效率。2006年，Duan等[3]提出了多接收者簽密的思想。隨著簽密問題的關注度不斷提高，在此之后有很多國內外學者提出了一些新的簽密方案[4-11]，簽密算法不斷得到創新和完善。

隨著信息技術的不斷發展，當人們面臨一個消息需要經過多個簽密者共同簽密然后再發送給接收者的問題時，對于多簽密方案的研究逐步走進人們的視野。2001年，Mitomi等[12]提出了一種并沒有給出其方案安全性證明的多簽密方案。張波等[13]于2010年提出了一種新的基于身份的無隨機預言機的多簽密方案，但通過計算和分析比較得知其方案的計算效率不高。

在張波[13]和李聰[14]等提出的方案的基礎上并參考其他有關文獻方案，文中提出了一種新的在標準模型下基于身份的多簽密方案。通過效率分析，當簽密者的人數為n(n>1)時，在簽密過程中的冪運算的計算次數比張波[13]和李聰[14]等的方案少了n-1個，并在文中給出了相關安全性的證明。

1 相關基礎

1.1 雙線性對

設G1,G2分別是一個階為大素數q的雙線性循環群，p是群G1的生成元，稱e:G1×G1→G2是一個雙線性映射，并且滿足以下性質。

(2)非退化性：存在P,Q∈G1，使得e(P,Q)≠1。

(3)可計算性：存在一個有效的算法在多項式時間內計算e(P,Q)。

1.2 困難問題假設

1.3 簽密模型

基于身份的多簽密方案通常包括四個階段：

(2)密鑰提取階段(extract)：由PKG將給定用戶U的身份IDu生成與之相對應的私鑰du，然后通過秘密渠道發給用戶U。

(3)多簽密階段(multi-signcrypt)：算法通過多個發送者的私鑰dAi、接收者Bob的身份IDB和消息m，生成密文σ。

(4)解簽密階段(unsigncrypt)：該算法由接收者Bob執行，通過輸入公開系統參數、自己的私鑰dB、多個發送者的身份IDAi以及密文σ，輸出明文消息m或者該密文是無效的提示。

2 文中方案

系統建立階段(setup)：令G、GT是兩個雙線性循環群，這兩個群的階均為素數q，群的規模由安全參數k決定，g是群G的生成元，雙線性映射e：GG→GT。Hu和Hm是兩個抵抗碰撞Hash函數，這兩個函數的功能是可以將長度任意的身份(ID)和消息(m)映射成文中方案所要求的長度，用符號表示為：Hu：{0,1}*→{0,1}nu，Hm：{0,1}*→{0,1}nm。隨機選擇α∈Zq，g2∈G，并且計算g1=gα∈G。隨機選擇u'∈Zq,m'∈G，定義向量Uu=(ui)，其長度為nu，定義向量Mm=(mi)，其長度為nm，其中ui∈RZq，mi∈RG。然后定義ω=e(g1,g2)。最后得到系統公共參數：π={G,GT,e,g,g1,g2,u',Uu,m',Mm,Hu,Hm}；系統主密鑰為

密鑰提取階段(extract)：通過Hu函數將用戶j的IDj映射成一個長度為nu的比特串，記I[i]是IDj第i位比特，記Uj?{1,2,…,nu}為I[i]=1的下標i的集合。PKG隨機選擇rj∈Zq，然后計算用戶j的密鑰：

因此，可以計算簽密者UAi(i=1,2,…,n)和接收者B的私鑰：

多簽密階段(multi-signcryption)：用戶u采用類似密鑰提取階段中同樣的方法獲得Mj集合,即Mj∈{1,2,…,nm}；PKG隨機選擇ri∈Zp，之后對消息m進行簽名。

(1)計算σi1=e(g2,g)ri

(2)σi2=dAi2

(4)將(σi1,σi2,σi3)發送給指定的簽密者Cindy，假設Cindy是第j個簽密者，則令其選擇的隨機數為rC，然后計算：

M=Hm(m||ω)

c=m⊕H(ω)

σ2={σi2|i=1,2,…,n}

σ4=grC

最終得到的簽密密文為σ=(c,σ1,σ2,σ3,σ4)。

解簽密階段(unsigncrypt)：接收者Bob在收到密文之后，將依照以下算法對密文進行解密：

計算：ω=e(σ4,dB1)；m=c⊕H(ω)；M=H(m‖ω)。

如果下面等式成立，則Bob就接收消息：

3 安全性分析

3.1 正確性

方案的正確性證明如下：

e(σ3,g)=

3.2 安全性

證明：假設挑戰者C收到一個實例(g,ga,gb,gc,α∈GT)，該實例是一個隨機的DBDH問題，目標是判定α=e(P,P)abc是否成立，C可以將Λ作為子程序調用，文獻[15-16]提出的思想作為此方案的證明。

系統參數設置：

挑戰者C設置lu=2(qE+qS+qU),lm=2qS。

(1)隨機選擇2個整數ku和km,其中0≤ku≤nu,0≤km≤nm；

(2)隨機選擇一個整數x'∈Zlu，一個nu維向量X=(xi),xi∈Zlu；

(3)隨機選擇一個整數z'∈Zlm，一個一維向量Z=(zi),zi∈Zlm；

(4)隨機選擇2個整數y',w'∈Zq，一個nu維向量Y=(yi),yi∈Zq和一個nm維向量W=(wi),wi∈Zq。

為了便于分析，對消息u和消息m定義如下函數：

挑戰者構造參數：

g1=ga,g2=gb

階段1：挑戰者C回答敵手Λ的詢問。

由F(u)=0modq，得F(u)=0modlu；由F(u)≠0modlu，得到F(u)≠0modq。

只有當F(u)≠0modlu不等式成立時，挑戰者C才能夠成功模擬這樣一個私鑰。

(2)多簽密詢問：敵手Λ隨時都能夠對明文m，每個簽密者的身份IDA1,IDA2,…,IDAn以及接收者的身份IDB進行詢問，然后對F(uAi)≠0modlu進行判斷，若不等式成立就按照密鑰詢問算法產生關于身份uAi的密鑰，再通過運行算法Multi-Signcrypt(m,dA1,dA2,…,dAn,IDB)來對Λ的詢問進行應答。

(3)解簽密詢問：敵手Λ隨手都能夠對密文σ進行解簽密詢問。然后對F(uB)≠0modlu進行判斷，若不等式成立，就按照密鑰提取算法產生身份uB的密鑰，然后通過運行算法Unsigncrypt(σ,dB,IDA1,IDA2,…,IDAn)來應答Λ的詢問。

模擬游戲成功。

猜測：最后，敵手Λ給出了猜測b'，其中b'∈{0,1}。若b'=b，則敵手Λ贏得了游戲。

根據上述過程，達到下面4個條件才能模擬成功：

(1)在密鑰詢問過程中須滿足F(u)≠0modlu。

(2)多簽密詢問中滿足F(ui)≠0modlu,i∈[1,n]。

(3)在解簽密詢問中須滿足F(uB)≠0modlu。

為了清晰地表達，假設qI≤qE+qS+qU，定義：

Pr[A']=Pr[F(u*)=0modp]=Pr[F(u*)=

0modlu]·Pr[F(u*)=

0modp|F(u*)=0modlu]=

另一方面，對于任意i,Ai和A'也是相互獨立。

結合以上這些結果，可以得到：

定理2：在CDH困難問題的假設前提下，提出新的多簽密方案滿足在適應性選擇消息攻擊下存在不可偽造性。

證明：假設存在一個偽造者Λ能夠成功偽造一個有效的簽密密文，那么可以通過Λ來構造一個挑戰者C，然后使挑戰者C來解決CDH問題。挑戰者可以通過使用證明密文不可區分性中參數設定的方法來設定公共參數，即C設定g1=ga,g2=gb。

3.3 效率分析

將文中方案與文獻[4]和文獻[13]中的算法進行分析比較，計算效率方面主要考慮計算消耗比較大的運算，主要有雙線性對運算、冪運算以及數乘運算。為便于分析，將這三種運算分別用P,E和M表示。通過計算分析可知，簽密者為1人時，文中方案的效率同文獻[13]一致，但當簽密者的人數大于1時，文中方案的效率更高并且計算規模也相對減小。具體的對比數據如表1所示。

4 結束語

通過對以往提出的多簽密方案的研究，在效率方面進行分析并改進，提出了新的標準模型下基于身份的多簽密方案，并且證明新方案具有不可區分性和不可偽造性。該方案在多個簽密者的情況下，減少了其簽密過程中的多個冪運算，同時降低了計算的規模，從而進一步提高了簽密的效率。對于密文長度的縮短和運算規模以及通信開銷的減小，將會在今后的工作中繼續深入研究。