通用可復合的ElGamal型廣播多重簽密協(xié)議

李建民 俞惠芳 謝 永

1(青海省氣象臺 西寧 810001)2(西安郵電大學通信與信息工程學院 西安 710121)3(青海師范大學計算機學院 西寧 810008)4(青海大學計算技術與應用系 西寧 810003)

多重簽名[1]是指2個以上的簽名者對同一則消息進行簽名,同時要求簽名的長度不會因為簽名者數(shù)目增多而呈線性增長,該類方案在電子商務領域被廣泛應用.目前多重簽名主要使用RSA(rivest shamir adleman)[2]、ElGamal[3-4]、雙線性對[5]、離散對數(shù)[6-7]等思想來設計.1994年Harn[8]提出了Meta-ElGamal多重簽名.1996年Wu等人[9]依據(jù)簽名的簽署順序不同,將多重簽名區(qū)分為順序多重簽名和廣播多重簽名.順序多重簽名意味著簽名者必須按照特有的順序依次對消息進行簽名;廣播多重簽名是指簽名者不必拘泥于固有的順序,按廣播的方式對消息進行簽名,由收集者合并且輸出簽名.廣播多重簽名相比順序多重簽名應用更為廣泛,ElGamal 型多重簽名的安全性基于DL(discrete logarithm)問題的難解性,滿足不可偽造性,缺點是不具備簽名者的身份驗證,不能抵制多個簽名者的聯(lián)合攻擊.

1997年Zheng[10]提出了簽密方案.簽密方案相對于傳統(tǒng)的簽名方案而言,能夠同時完成簽名和加密2項功能.簽名方案只是確保設計方案的不可偽造性,在安全性分析時,只要方案滿足選擇消息攻擊的不可偽造性,那么就說設計的方案是語義安全的.簽密方案能夠在一個合理的邏輯步驟內(nèi)同時完成簽名和加密，在安全性分析時,不僅要分析方案的保密性,還要分析方案的不可偽造性.

2002年Baek等人[11]對Zheng的簽密方案進行了改進,同時給出了隨機預言模型下的安全性證明.2011年Fan等人[12]改進了2002版本的簽密方案,在Hash函數(shù)的輸入中添加了接收方和發(fā)送方的公鑰.近年來,越來越多的學者將簽密和具有特殊性質(zhì)的簽名結(jié)合起來進行研究,使用不同的認證方法來認證用戶公鑰[13-19].2016年周才學[20]指出很多簽密方案還存在安全問題,同時他認為在解簽密算法的驗證等式中不應出現(xiàn)明文信息,加密部分應該包含發(fā)送者的公鑰或身份信息,簽名部分應包含接收者的公鑰或身份信息,在無證書密碼體制的簽名部分中不要讓部分私鑰和秘密值之間只是存在簡單的線性關系.

UC(universally composalble)安全框架[21]滿足協(xié)議的模塊化設計要求,可以單獨用來設計協(xié)議.只要協(xié)議滿足UC安全性,則可以保證和其他協(xié)議并發(fā)組合運行的安全性.設計一個UC安全協(xié)議,首先要將協(xié)議所希望完成的功能抽象為一個理想函數(shù),該理想函數(shù)相當于現(xiàn)實世界中一個不可攻破的可信第三方.2003年Canetti等人[22]糾正了自己在2001年提出的簽名理想函數(shù)的定義,通過添加SID(session identifier)來編碼簽名者的身份,允許被收買的簽名者對合法的簽名進行驗證,對公鑰、簽名、驗證消息進行儲存;2007年Kristian等人[23]利用用戶友好交互提出了一個安全消息傳遞理想函數(shù),給出了簽密的理想函數(shù);2012年Canetti等人[24]提出了不經(jīng)意傳輸(oblivious transfer, OT)協(xié)議的理想函數(shù),同時給出了使用OT協(xié)議的雙向認證協(xié)議的通用方法.國內(nèi)對UC安全的研究也取得了一些成果,馮濤等人[25]利用可否認加密體制和可驗證平滑投影Hash函數(shù)提出了一個UC安全的高效不經(jīng)意傳輸協(xié)議;蘇婷等人[26]基于密鑰注冊模型形式化定義了簽密協(xié)議的安全模型(即簽密協(xié)議的理想函數(shù)),設計了一般化的簽密協(xié)議,給出了UC框架下的證明;張忠等人[27]形式化定義了信息處理集合和無線射頻識別(radio frequency identification, RFID)組證明的理想函數(shù),然后設計了一個組證明RFID協(xié)議,證明了該協(xié)議安全地實現(xiàn)了理想功能;田有亮等人[28]利用身份簽密機制提出了一個UC安全的群通信協(xié)議,解決了多播群組通信的組合安全問題,之后,他們又設計了一個通用可組合的安全多方計算協(xié)議[29],即在UC框架下能實現(xiàn)公平的安全兩方計算協(xié)議,使人們認為的兩方公平安全計算不能實現(xiàn)的問題得到解決.

本文結(jié)合自認證公鑰和Meta-ElGamal多重簽名協(xié)議的思想,在UC框架下設計了一個ElGamal型廣播多重簽密(ElGamal broadcasting multi-sign-cryption, EBMSC)協(xié)議,進而在UC安全框架下分析了該協(xié)議的安全性.也給出了ElGamal型廣播多重簽密協(xié)議的UC安全性證明.

1 預備知識

1.1 困難假設

1.2 UC安全框架

UC安全框架是由現(xiàn)實模型、理想模型和混合模型組成.在UC框架中,用交互式圖靈機(inter-active turing machine, ITM)來描述協(xié)議的參與方、敵手和環(huán)境機等實體.每個ITM的運行都被限定在概率多項式時間內(nèi).在現(xiàn)實模型中,包括了參與方P、敵手A、協(xié)議π和環(huán)境機Z等實體,參與方P不僅誠實地執(zhí)行協(xié)議π,而且相互之間還可以直接通信.在理想模型中,包括了參與方P、模擬者S、理想函數(shù)F和環(huán)境機Z等實體.和現(xiàn)實模型不一樣的是,參與方P相互之間不能直接通信,而是通過理想函數(shù)F來轉(zhuǎn)發(fā)信息,現(xiàn)實模型和理想模型的外部環(huán)境Z相同.由于模塊化的設計思想,只要證明某個協(xié)議能滿足UC安全性,則和其他協(xié)議并發(fā)運行也能保證其安全性.

定義3.不可區(qū)分性[21].X和Y是2個不可區(qū)分的二元分布集合(記作X≈Y),如果任何c∈N都有k0∈N,使得所有k>k0和所有的a,都有:

|Pr(X(k,a)=1)-Pr(Y(k,a)=1)|

定義4.UC仿真[21].設n∈N,令F是理想函數(shù),π具有n個參與方的協(xié)議,τ是現(xiàn)實中某類敵手.若對任何現(xiàn)實攻擊者A∈τ都存在一個理想過程中的敵手S,使得任何環(huán)境機Z都不能區(qū)分它是與(π,A)交互還是與(F,S)交互，則稱π安全實現(xiàn)了F,記作:

IDEALF,S,Z≈REALπ,A,Z.

定義5.組合定理[21].令F和G是理想函數(shù),π是F-混合模型下的一個協(xié)議,ρ協(xié)議在G-混合模型下可以安全地實現(xiàn)F.則對于任何敵手AG,都存在一個AF,使得對于任何環(huán)境機Z,都有:

1.3 基于離散對數(shù)的多重簽名回顧

Harn[8]利用離散對數(shù)提出了一種有效的多重簽名方案.假設n個簽名者對同一消息m進行簽名.

2) 簽名者ui用秘鑰zi和ki對消息m運行簽名算法.即si=(zi(m′+r)-ki) modp,其中0≤si≤p-2和m′=f(m).簽名者把元組(m,si)發(fā)送給消息收集者.

4) 消息收集者將對通過驗證的消息進行合并：s=(s1+s2+…+sn) modp，得到完整的簽名(r,s).

6) 驗證ym′+r=rαsmodp,這里m′=f(m).

2 EBMSC協(xié)議的形式化定義

2.1 EBMSC算法定義

一個EBMSC協(xié)議由4個算法組成:參與方包括消息發(fā)起者或簽密收集者UC、簽密者U1,U2,…,Un、接收者UV.

系統(tǒng)設置算法:輸入安全參數(shù)1k,生成系統(tǒng)主密鑰s和系統(tǒng)參數(shù)params.

密鑰提取算法:身份IDu的用戶隨機選擇秘密鑰生成其公鑰yu,而密鑰生成中心(key generator central, KGC)隨機選擇秘密鑰ηu,然后根據(jù)用戶身份IDu和公鑰yu生成其部分私鑰Tu,之后安全的形式發(fā)給用戶.用戶收到部分私鑰Tu后,計算完整私鑰xu.

多重簽密算法:輸入系統(tǒng)的參數(shù)params、明文m、簽密者Ui的私鑰xi及接收者UV的公鑰yV,輸出多重簽密密文σ.

解簽密算法:輸入密文σ、參數(shù)params、簽密者Ui的公鑰yi及接收者UV的私鑰xV,輸出明文m或者解簽密符號⊥.

2.2 安全模型

一個EBMSC協(xié)議有2類敵手,即A1和A2.敵手A1無法得到系統(tǒng)的主密鑰,但是可以替換用戶的公鑰(敵手A1相當于模擬了不誠實的用戶);敵手A2可以得到系統(tǒng)的主密鑰,但不能替換用戶的公鑰(敵手A2相當于模擬了惡意的KGC).

定義6.如果存在任何多項式有界的敵手A1和A2贏得游戲IND-CCA2-I和IND-CCA2-II的優(yōu)勢是可忽略的,則稱EBMSC 協(xié)議是具有適應性選擇密文攻擊下的不可區(qū)分性(indistinguishability against adaptive chosen ciphertext attacks, IND-CCA2).

IND-CCA2-I:這是挑戰(zhàn)者C和敵手A1之間的交互游戲.

初始化.C運行系統(tǒng)設置算法得到系統(tǒng)參數(shù)params和系統(tǒng)主密鑰s,之后將系統(tǒng)參數(shù)params發(fā)給A1,但保留主密鑰s.

階段1.A1進行多項式有限次詢問.

公鑰詢問:當收到A1的公鑰詢問時,C運行密鑰提取算法中的用戶公鑰生成算法得到y(tǒng)i,返回給A1.

部分私鑰提取詢問:A1可以請求身份IDu的部分私鑰詢問,C運行密鑰提取算法中的部分密鑰生成算法得到Tu,之后把Tu返回給A1.

私鑰提取詢問:A1可以請求身份IDu的私鑰詢問,C運行密鑰提取算法中的私鑰生成算法得到xu,之后把xu返回給A1.

簽密詢問:A1收到(IDi,IDV,m)的簽密詢問時,C通過調(diào)用簽密算法得到多重簽密密文σ,之后將σ發(fā)給A1.

解簽密詢問:A1收到(IDi,IDV,σ)時,C通過調(diào)用解簽密算法得到的消息mi之后返給A1.

最后,輸出δ′={0,1}作為對δ的猜測.如果δ′=δ,則A1贏得游戲.

定義7.如果存在任何多項式有界的敵手A1和A2贏得游戲UF-CMA-I和UF-CMA-II的優(yōu)勢是可忽略的,則稱EBMSC協(xié)議是具有適應性選擇消息攻擊下的不可偽造性(unforgeability against adaptive chosen message attacks, UF-CMA).

UF-CMA-I:C和偽造者A1之間的交互游戲.

初始化.C運行系統(tǒng)設置算法得到系統(tǒng)參數(shù)params和系統(tǒng)主密鑰s,之后將系統(tǒng)參數(shù)params發(fā)給A1,但保留主密鑰s.

訓練.A1進行的多項式有界次詢問和定義6中IND-CCA2-I的階段1一樣.

UF-CMA-II:C和偽造者A2之間的交互游戲.

初始化.C運行系統(tǒng)設置算法得到系統(tǒng)參數(shù)params和系統(tǒng)主密鑰s,之后將系統(tǒng)參數(shù)params發(fā)給A2,但保留主密鑰s.

訓練.A2進行的多項式有界次詢問和定義6中IND-CCA2-II游戲的階段1一樣.

3 一個具體的EBMSC協(xié)議

3.1 初始化(Setup)

3.2 密鑰生成(Extract)

3.3 廣播多重簽密(MultiSC)

2)h=H2(m,α).

4)Ci=m⊕H3(Wi).

5)μi=H4(m,Ti,TV,Wi).

6)βi=(ki(μi+Ti+hα)-ri) mod (p-1).

8) 簽密收集者UC將進一步輸出簽密密文σ=(α,βi,h,Ti,TV,{C1,C2,…,Cn}) 給接收者UV.

3.4 解簽密(USC)

接收者UV收到簽密密文σ后,執(zhí)行步驟.

2)m=Ci⊕H3(Wi).

3)μi=H4(m,Ti,TV,Wi).

3.5 正確性分析

可通過驗證等式確保所提協(xié)議的正確性:

3.6 ROM下的安全性分析

3.6.1 保密性

在隨機預言模型(ROM)下的安全性分析,我們參考文獻[18]的思路.

定理1.在ROM中,如果沒有任何多項式有界的敵手A1能以不可忽略的優(yōu)勢ε贏得定義6中的游戲IND-CCA2-I(至多進行qi次Hi詢問(i=1,2,3,4),qPK次公鑰替換詢問,qPSK次部分私鑰提取詢問,qSK次私鑰提取詢問,qSC次簽密詢問,qUSC次解簽密詢問),則存在一個挑戰(zhàn)者C能至少以ε′的優(yōu)勢解決CDH問題,這里:

params={p,g,l,PPub=ga,H1,H2,H3,H4},

同時將params發(fā)給A1.在交互游戲中,表L1到L4用于記錄H1至H4的詢問與應答值,Lk用于記錄公私鑰的詢問與應答值.

階段1.A1進行多項式有界次適應性詢問.

H3詢問:A1發(fā)出H3詢問.C檢查元組(Wi,h3)是否存在于L3表中,如果存在,則返回h3;否則,C隨機選取h3∈R{0,1}l,然后將h3發(fā)給A1,記錄(Wi,h3)到L3中.

私鑰詢問:A1詢問身份IDi的私鑰.假設已經(jīng)詢問過H1預言機.若ψ=0,則返回完整私鑰xi=kiTimodp;否則,放棄仿真,之后將私鑰添加到Lk中.

多重簽密詢問:A1可對任何消息m及簽密人的身份IDi、接收者的身份IDV進行簽密詢問.假設在此之前已經(jīng)做過Hash函數(shù)值詢問和密鑰提取詢問.如果ψ=0,則正常執(zhí)行多重簽密算法;否則執(zhí)行操作:

繼續(xù)執(zhí)行操作:

3) 計算Ci=m⊕H3(Wi).

4) 計算μi=H4(m,TV,Ti,Wi).

5) 計算βi=(ki(μi+Ti+hα)-ri) mod (p-1).驗證：

是否成立.如果成立,則計算:

7) 輸出σ=(α,β,h,Ti,TV,{C1,C2,…,Cn}).

則通過解簽密;否則認為不合法.

階段2.A1可以像階段1那樣進行多項式有界次適應性詢問.但是要求身份IDV的私鑰仍然不能被詢問,此外不能做σ*的解簽密詢問.

作為CDH問題實例的解答,原因如下:

證畢.

定理2.在ROM中,如果沒有任何多項式有界的敵手A2能以不可忽略的優(yōu)勢ε贏得定義6中的游戲IND-CCA2-Ⅱ(至多進行qi次Hi詢問(i=1,2,3,4),qPK次公鑰替換詢問,qSK次私鑰提取詢問,qSC次簽密詢問,qUSC次解簽密詢問),則存在一個挑戰(zhàn)者C能夠至少以ε′的優(yōu)勢解決CDH問題,這里:

params={p,g,l,PPub=gs,H1,H2,H3,H4},

同時將params發(fā)給A2.在游戲中,表L1到L4用于記錄H1至H4的詢問與應答值,Lk用于記錄公私鑰的詢問與應答值.

階段1.除了部分私鑰詢問,其他詢問同定理1.

階段2.A2可以像階段1那樣進行多項式有界次適應性詢問.但是要求身份為IDV的私鑰仍然不能被詢問,并且不能做關于σ*的解簽密詢問.

作為CDH問題實例的應答,因為:

?

證畢.

3.6.2 不可偽造性

定理3.如果任何多項式有界的敵手A1和A2贏得定義7中的游戲UF-CMA-I和UF-CMA-II的優(yōu)勢是可忽略的,則EBMSC協(xié)議具有適應性選擇消息攻擊下的不可偽造性(至多進行qi次Hi詢問(i=1,2,3,4),qPK次公鑰替換詢問,qPSK次部分私鑰提取詢問,qSK次私鑰提取詢問,qSC次簽密詢問,qUSC次解簽密詢問),在UF-CMA-I中,則存在一個挑戰(zhàn)者C至少能夠以

的優(yōu)勢解決離散對數(shù)問題;在UF-CMA-II中,則存在一個挑戰(zhàn)者C至少能夠以

的優(yōu)勢解決離散對數(shù)問題.

在交互游戲開始之時,游戲開始后,C運行Setup(1k),得到參數(shù):

params={p,g,l,PPub,H1,H2,H3,H4},

并將params發(fā)給A1.在游戲中,表L1到L4記錄H1至H4的預言機,Lk用于追蹤公私鑰的詢問與應答值.

詢問階段.和定理1相同.

偽造. 對于不同的敵手偽造的過程不一樣.

②PPub=ga.

調(diào)用預言機H1可以得到h1,輸出:

作為離散對數(shù)問題實例的解答,原因如下:

分析C成功解決離散對數(shù)問題的概率,A1沒做過IDi的私鑰或部分私鑰詢問的概率為

③yi=gamodp.

分別調(diào)用預言機H2和H4得到h和h4.C輸出:

作為離散對數(shù)問題實例的應答,因為:

?

分析C成功解決離散對數(shù)問題的概率,A2沒有作過私鑰詢問的概率為1eqSK,σ*通過解簽密驗證的概率為1qUSC,所以C解決離散對數(shù)問題的概率為ε′,這里:

證畢.

4 EBMSC協(xié)議的UC安全性分析

4.1 理想函數(shù)FEBMSC

理想模型中,EBMSC協(xié)議的理想函數(shù)FEBMSC、參與方P1,P2,…,Pn及敵手S一起運行,執(zhí)行過程如下:

① 在收到(KGC,Setup,sid)請求后驗證,若驗證sid=(KGC,sid′)成功,則將此消息發(fā)送給敵手S.

② 在收到敵手S回復的(Setup,Verify,sid,params)后,記錄下Verify.

③ 在收到Pi的(Key,sid,Pi)請求后,驗證sid=(Pi,sid′),若驗證成功,則將此消息發(fā)送給敵手S,然后收到敵手S回復的(Pi,sid,yi).

④ 在收到PV的(Key,sid,PV)請求后,驗證sid=(PV,sid′),若驗證成功,則將此消息發(fā)送給敵手S.在收到敵手S回復的yV后,將yV發(fā)送給Pi.一旦收到來自Pi的消息(Key,sid,PV),則將此消息發(fā)送給敵手S,從敵手S處收到y(tǒng)i時,將yi發(fā)送給PV.之后,忽略所有的(Key,sid,PiPV).

當從敵手S處收到σ時,將(MultiSC,sid,m,σ)給PV,并存儲(m,σ).

⑥ 在收到接受者PV的(USC,sid,σ,yi)請求后,驗證sid=(PV,sid′),若驗證不成功,則將忽略發(fā)送過來的消息;否則,執(zhí)行如下:

如果(m,σ)已經(jīng)記錄過,則驗證Verify((params,sid,m,σ),f=1),并把(m,f)發(fā)給S.

否則,將(USC,sid,σ,yi)發(fā)給敵手S,并從敵手S處得到m,并以(m,f=0)的形式發(fā)送給PV.

4.2 協(xié)議πEBMSC

下面是設計的ElGamal型廣播多重簽密協(xié)議πEBMSC=(Setup,Extract,MultiSC,USC),在UC框架下該協(xié)議運行如下:

① 一旦收到(KGC,Setup,sid)消息請求,則驗證sid=(KGC,sid′),運行Setup(1k)得到(s,params),返回參數(shù)params.

② 收到(U,Key,sid),運行Extract(params,s,ID),得到(xID,yID),然后將(xID,yID)返回.

③ 收到(MultiSC,m,yV,sid)消息請求后,運行MultiSC(params,m,xi,yV)→σ,并將σ返回.

④ 收到(USC,sid,σ),運行USC(params,m,yi,xV),得到消息m,若收到(Verify,sid,m,σ)請求,則運行Verify(params,sid,m,σ)→f,并返回f的值.

4.3 UC框架下協(xié)議的安全性證明

定理4.協(xié)議πEBMSC實現(xiàn)了廣播多重簽密理想函數(shù)FEBMSC.

證明. 假設A為現(xiàn)實模型中的敵手.現(xiàn)在構(gòu)造一個理想敵手S,使得對于任何環(huán)境機Z都不能區(qū)分是與FEBMSC和S在理想模型下的交互,還是與πEBMSC和A在現(xiàn)實過程中的交互.理想敵手S、環(huán)境機Z、敵手A以及參與方P1,P2,…,Pn一起運行.

構(gòu)造敵手S:在理想過程中,敵手S可以調(diào)用A的副本來與FEBMSC和S交互,模擬A在現(xiàn)實過程與協(xié)議πEBMSC的交互.首先,敵手S把輸出帶上的內(nèi)容寫到A的輸入帶上,并把A輸出帶的內(nèi)容拷貝到Z的輸出帶上.

模擬簽密者Pi和接收者PV都不被入侵.當S收到FEBMSC的消息(Setup,sid),運行Setup算法生成公鑰yV,并把消息(Verify,v)輸出給FEBMSC.當S收到來自FEBMSC的一個消息(MultiSC,sid,m),運行多重簽密算法MultiSC,得到簽密σ并把(MultiSC,sid,m)輸出給FEBMSC.當S收到來自FEBMSC的一個消息(Verify,sid,m,σ,v′)后,運行驗證簽名算法Verify,得到驗證結(jié)果f,把(Verify,sid,m,f)輸出給FEBMSC.現(xiàn)實環(huán)境下簽密者對消息進行簽密,并將簽密結(jié)果發(fā)送給接收者.接收者驗證簽密的有效性.理想環(huán)境中仿真器S對真實過程進行仿真,仿真簽密過程和驗證過程,同樣發(fā)送簽密和驗證結(jié)果,因而,環(huán)境機Z不能區(qū)分出是FEBMSC與S在理想模型中的交互,還是πEBMSC與A在現(xiàn)實過程中的交互.

模擬簽密者Pi被入侵.敵手S模擬A偽裝成參與方Pi把(Setup,sid)發(fā)送給FEBMSC.同樣,當S收到來自FEBMSC的消息(Extract,sid)后.運行密鑰生成算法Setup,得到簽密者公鑰yi并將其返回給FEBMSC.當S收到來自FEBMSC的消息(MultiSC,sid),運行多重簽密算法,得到密文并將其返回給FEBMSC.S模擬A入侵參與方Pi,并將(MultiSC,sid,m′)發(fā)送給FEBMSC.同樣,當S接收到(MultiSC,sid,m′)時,可以得到多重簽密σ′,即把(MultiSC,sid,m′,σ′)發(fā)送給FEBMSC.由此看來,環(huán)境Z并不能區(qū)分現(xiàn)實過程和理想模型.

模擬接收者PV被入侵.若參與方PV被收買,敵手S可以模擬參與方的身份把(Verify,sid,m′,σ′,v′)發(fā)送給FEBMSC,隨后,當S接收到(Verify,sid,m′,σ′,v′)時,計算驗證結(jié)果f,把(Verify,sid,m′,σ′,v′,f) 發(fā)送給FEBMSC.此時,環(huán)境機Z不能區(qū)分(m,σ)與(m′,σ′).

模擬簽密者Pi和接收者PV都被入侵.當多重簽密者Pi和解簽密者PV都被攻陷時,S將獲得雙方的所有輸入信息,即Z可產(chǎn)生真實的數(shù)據(jù)來仿真協(xié)議的運行.

綜合上述4種情形,環(huán)境機Z不能區(qū)分出是FEBMSC與S在理想模型中的交互,還是πEBMSC與A在現(xiàn)實過程中的交互.即協(xié)議πEBMSC能夠?qū)崿F(xiàn)廣播多重簽密理想函數(shù)FEBMSC.

證畢.

定理5.在UC安全框架下,協(xié)議πEBMSC滿足選擇消息攻擊下的不可偽造性.

證明. 假設存在偽造者F,則構(gòu)造環(huán)境機Z和敵手A,使得對于任何敵手A,Z都以不可忽略的概率區(qū)分它是與(πEBMSC,A)交互還是與(FEBMSC,S)交互.

構(gòu)造環(huán)境機Z.當收到來自A的多重簽密請求時,則Z激活Pi,然后輸出多重簽密密文σ,并返回給A.當收到來自A的解簽密請求時,Z激活Pi,并輸出(m,f)給A.

構(gòu)造敵手A.當A要求對消息m進行多重簽密時,敵手A首先要求環(huán)境機Z對m進行多重簽密,然后把多重簽密密文σ給F;當F需要對σ′解簽密時,敵手A首先要求環(huán)境機Z對σ′進行解簽密,然后把(m′,f)返回給A,再發(fā)給偽造者F.一旦F收到了m′,并且f=1,則F偽造的多重簽密是有效的,此時,Z輸出f=1.顯然,如果F以可忽略的概率贏得了 定理3中的UF-CMA-I和UF-CMA-II游戲,則F能夠成功地偽造出有效的F, 假設偽造者F以可忽略的概率存在,則Z以可忽略的概率輸出f=1.而在理想模型中,Z輸出f=1的概率總是等于0.換句話說,如果存在這樣的偽造者F,Z總以可忽略的概率區(qū)分它是與(πEBMSC,A)交互還是與(FEBMSC,S)交互,故與定理5的假設矛盾.所以,不存在這樣的偽造者F,也就是說,在UC安全框架下,協(xié)議πEBMSC滿足選擇消息攻擊下的不可偽造性.

證畢.

5 性能分析

ElGamal型廣播多重簽密協(xié)議的計算開銷主要集中在模指數(shù)和Hash函數(shù)運算.表1中E表示1次模指數(shù)運算,H表示1次Hash函數(shù)運算,M表示1 次乘法運算.本文方案與文獻[30-33]中的方案效率比較如表1所示.從表1中看出,本文分案明顯好于文獻[30,32-33],并且本文還實現(xiàn)了廣播多重簽密功能.本文與文獻[31]的效率相當, 但文獻[31]只實現(xiàn)了多重數(shù)字簽名,而本文方案不僅實現(xiàn)了多重簽密功能,還在UC框架證明了該協(xié)議是安全的.

Table 1 Efficiency of this Paper Compared with Others References表1 本文方案與其他文獻的效率比較

Notes: E: 1 exponential operation; M: 1 multiplication operation; H: 1 hash operation.

6 總 結(jié)

目前設計的ElGamal型廣播多重簽密協(xié)議的安全性一般是基于DL問題的難解性,雖然滿足了不可偽造性,但是不具備簽名者的身份驗證,使得該類協(xié)議容易遭受多個簽名者的聯(lián)合攻擊.本文設計了一個新的ElGamal型廣播多重簽密協(xié)議,由于本文是采用自認證方式來認證用戶的公鑰,克服了密鑰管理問題以及能夠抵抗文獻[5-7]的攻擊.在隨機預言模型中證明了該協(xié)議在離散對數(shù)和CDH假設下是語義安全的.為了使所提協(xié)議適應更加復雜的網(wǎng)絡環(huán)境,本文引入UC安全技術,而在UC安全框架下分析了該協(xié)議的安全性.我們定義了ElGamal型廣播多重簽密協(xié)議的理想函數(shù)FEBMSC,進而證明了UC安全的ElGamal型廣播多重簽密協(xié)議的通用可組合安全性.下一步將對集合相交協(xié)議進行研究.