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

吳振國，祁正華，王 翔

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

0 引 言

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

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

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

1 相關(guān)基礎(chǔ)

1.1 雙線性對

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

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

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

1.2 困難問題假設(shè)

1.3 簽密模型

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

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

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

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

2 文中方案

系統(tǒng)建立階段(setup)：令G、GT是兩個雙線性循環(huán)群，這兩個群的階均為素數(shù)q，群的規(guī)模由安全參數(shù)k決定，g是群G的生成元，雙線性映射e：GG→GT。Hu和Hm是兩個抵抗碰撞Hash函數(shù)，這兩個函數(shù)的功能是可以將長度任意的身份(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)。最后得到系統(tǒng)公共參數(shù)：π={G,GT,e,g,g1,g2,u',Uu,m',Mm,Hu,Hm}；系統(tǒng)主密鑰為

密鑰提取階段(extract)：通過Hu函數(shù)將用戶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)發(fā)送給指定的簽密者Cindy，假設(shè)Cindy是第j個簽密者，則令其選擇的隨機數(shù)為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 安全性

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

系統(tǒng)參數(shù)設(shè)置：

挑戰(zhàn)者C設(shè)置lu=2(qE+qS+qU),lm=2qS。

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

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

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

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

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

挑戰(zhàn)者構(gòu)造參數(shù)：

g1=ga,g2=gb

階段1：挑戰(zhàn)者C回答敵手Λ的詢問。

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

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

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

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

模擬游戲成功。

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

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

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

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

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

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

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

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

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

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

結(jié)合以上這些結(jié)果，可以得到：

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

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

3.3 效率分析

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

4 結(jié)束語

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