吳振國(guó)，祁正華，王 翔

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003)

0 引 言

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

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

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

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

1.1 雙線性對(duì)

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

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

(3)可計(jì)算性：存在一個(gè)有效的算法在多項(xiàng)式時(shí)間內(nèi)計(jì)算e(P,Q)。

1.2 困難問(wèn)題假設(shè)

1.3 簽密模型

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

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

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

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

2 文中方案

系統(tǒng)建立階段(setup)：令G、GT是兩個(gè)雙線性循環(huán)群，這兩個(gè)群的階均為素?cái)?shù)q，群的規(guī)模由安全參數(shù)k決定，g是群G的生成元，雙線性映射e：GG→GT。Hu和Hm是兩個(gè)抵抗碰撞Hash函數(shù)，這兩個(gè)函數(shù)的功能是可以將長(zhǎng)度任意的身份(ID)和消息(m)映射成文中方案所要求的長(zhǎng)度，用符號(hào)表示為：Hu：{0,1}*→{0,1}nu，Hm：{0,1}*→{0,1}nm。隨機(jī)選擇α∈Zq，g2∈G，并且計(jì)算g1=gα∈G。隨機(jī)選擇u'∈Zq,m'∈G，定義向量Uu=(ui)，其長(zhǎng)度為nu，定義向量Mm=(mi)，其長(zhǎng)度為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)：通過(guò)Hu函數(shù)將用戶j的IDj映射成一個(gè)長(zhǎng)度為nu的比特串，記I[i]是IDj第i位比特，記Uj?{1,2,…,nu}為I[i]=1的下標(biāo)i的集合。PKG隨機(jī)選擇rj∈Zq，然后計(jì)算用戶j的密鑰：

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

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

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

(2)σi2=dAi2

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

M=Hm(m||ω)

c=m⊕H(ω)

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

σ4=grC

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

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

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

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

3 安全性分析

3.1 正確性

方案的正確性證明如下：

e(σ3,g)=

3.2 安全性

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

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

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

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

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

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

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

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

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

g1=ga,g2=gb

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

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

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

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

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

模擬游戲成功。

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

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

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

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

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

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

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

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

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

另一方面，對(duì)于任意i,Ai和A'也是相互獨(dú)立。

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

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

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

3.3 效率分析

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

4 結(jié)束語(yǔ)

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