無證書簽密的通用可組合機制

王琳杰 田有亮

1(銅仁學(xué)院大數(shù)據(jù)學(xué)院 貴州 銅仁 554300) 2(貴州大學(xué)計算機科學(xué)與技術(shù)學(xué)院 貴州 貴陽550025) 3(貴州省公共大數(shù)據(jù)重點實驗室(貴州大學(xué)) 貴州 貴陽 550025)

0 引 言

簽密概念是Zheng[1]于1997年在17屆國際密碼學(xué)年會上首次提出，此概念實現(xiàn)了在一個邏輯步驟內(nèi)同時完成對消息的簽名和加密。與“先簽名后加密”的傳統(tǒng)方式相比，其在計算和通信方面的開銷大幅降低，是實現(xiàn)信息安全傳輸?shù)囊环N比較理想的方法。因此，該概念一經(jīng)提出就引起各國密碼學(xué)研究者的注意，并迅速成為密碼學(xué)界研究的熱點。在密碼學(xué)中，對信息的保密和認(rèn)證一直是該學(xué)科研究的重點，而簽密卻能很好地實現(xiàn)上述兩個要求，并且在實際的應(yīng)用中有著較好的計算和通信開銷，因此基于各種密碼體制下的簽密方案被提出[2-3]。

在傳統(tǒng)公鑰加密體制中，大多數(shù)通信方案都基于證書來實現(xiàn)，而證書則是參與通信各方的身份標(biāo)志(Identity document，ID)，它們都保存在一個稱為可信中心(CA)的機構(gòu)里面。如果想要與網(wǎng)絡(luò)中某人通信就要到CA中查找相應(yīng)人員的ID，但是在實際的運行中發(fā)現(xiàn)有不可信的CA進行偽造或者修改過期ID的操作，為此密碼界的學(xué)者想方設(shè)法解決不可信CA的問題。1984年，Shamir[4]在基于身份的公鑰加密體制方案中提出了一個密鑰管理問題，而AL-Riyami等[5]為了解決上述密鑰管理問題，于2003年首次提出一種無證書的公鑰密碼體制，其中用戶的私鑰是由用戶在KGC生成的主密鑰的基礎(chǔ)上隨機選取秘密值生成的，由此克服了傳統(tǒng)公鑰密碼體制中密鑰托管問題。

2008年Barreto等[6]首次提出無證書簽密(Certificateless signcryption，CLSC)的概念和形式化的定義，隨后國內(nèi)學(xué)者提出了很多無證書簽密方案[7-14]。文獻[12]為了提高運算效率提出了一種使用指數(shù)運算的無證書簽密方案，方案的機密性和不可否認(rèn)性是基于計算性Diffie-Hellman(CDH)和離散對數(shù)問題。文獻[15]基于非配對的廣義雙線性Diffie-Hellman(NGBDH)問題和Many Diffie-Hellman(MDH)問題提出了基于雙線性對的無證書簽密方案，方案在標(biāo)準(zhǔn)模型下證明了安全性。同樣，文獻[16]在隨機預(yù)言模型下證明了基于雙線性對的無證書簽密方案的安全性。除此之外，文獻[6-10]是基于雙線性映射提出的無證書簽密方案，而文獻[11-14]是基于不適用雙線性映射的無證書簽密方案。上述文獻研究的安全性證明要么是基于IND游戲進行證明，要么是在隨機預(yù)言機模型下進行證明，要么是在IND游戲和隨機預(yù)言機模型的結(jié)合下進行證明，這些協(xié)議的安全性證明只考慮其自身運行時的安全性，并沒有考慮與其他協(xié)議同時并行運行的情況。當(dāng)上述協(xié)議在作為一個系統(tǒng)的某個子協(xié)議或者一個比較復(fù)雜的協(xié)議的一個部分時，不一定仍能保證其自身的安全性。上述文獻沒有在通用可組合框架下研究無證書簽密方案安全性，因此本文在通用可組合框架下重新定義無證書簽密方案的安全性，以達到多協(xié)議協(xié)同運作環(huán)境下的無證書簽密方案的安全需求。

通用可組合框架[17](UC framework)是由Canetti提出，其最優(yōu)秀的性質(zhì)是模塊化設(shè)計思想，即該框架中被證明安全的協(xié)議之間進行并行運行時，仍能保證協(xié)議是安全的[18]。由于該框架具有協(xié)議之間進行并行運行的優(yōu)秀性質(zhì)，因此在此框架下許多密碼協(xié)議的安全性被重新研究，例如文獻[18-24]在UC框架下研究了門限簽名協(xié)議、多重數(shù)字簽名協(xié)議、代理重簽名協(xié)議、群組通信協(xié)議、安全多方計算協(xié)議、群簽名、自認(rèn)證盲簽名協(xié)議、分散電子投票協(xié)議，及基于身份的代理簽密協(xié)議等。

本文在UC框架下研究了無證書簽密協(xié)議問題，提出一種無證書的簽密機制。首先，本文定義了無證書簽名協(xié)議πCLSC；其次，在UC框架下定義了無證書簽密對應(yīng)的理想函數(shù)FCLSC；最后證明了該協(xié)議πCLSC安全實現(xiàn)理想函數(shù)FCLSC的充要條件是協(xié)議πCLSC滿足在適應(yīng)性選擇密文攻擊下的不可區(qū)分性。本文的貢獻如下：(1) 提出了通用可組合框架下無證書簽密協(xié)議模型，并設(shè)計了無證書簽密的理想函數(shù)FCLSC；(2) 構(gòu)造了一個安全實現(xiàn)理想函數(shù)FCLSC的無證書簽密協(xié)議πCLSC；(3) 基于理想函數(shù)FCLSC和離散對數(shù)問題給出一個具體的協(xié)議實例。

1 準(zhǔn)備知識

1.1 UC框架

UC框架由現(xiàn)實模型、理想模型、混合模型三個模型構(gòu)建而成。現(xiàn)實模型描述協(xié)議的真實運行情況，由現(xiàn)實協(xié)議π、環(huán)境Z、現(xiàn)實的敵手A之間的交互構(gòu)成。理想模型描述協(xié)議執(zhí)行的理想情況，由一個不可攻陷的理想函數(shù)F(它通過一組“可信中心”的指令來獲取所需的功能或規(guī)范)、虛擬參與者(Dummy parties)及理想攻擊者S組成，并利用F來保證協(xié)議的安全性。其中，參與者之間以及敵手S與參與者之間不直接通信；所有參與者和敵手S均與理想函數(shù)交互。在理想模型中，虛擬參與者將自己的輸入交給F，由F計算后將結(jié)果返回給參與者。如果現(xiàn)實模型中的協(xié)議可以訪問理想模型的某個理想函數(shù)，那么這個模型就是混合模型。如果協(xié)議π能訪問理想函數(shù)F，稱其為F-混合協(xié)議。

UC框架中，由于存在“仿真”使得現(xiàn)實模型可以訪問理想模型中的理想函數(shù)，從而將現(xiàn)實模型的安全規(guī)約到理想模型的安全。協(xié)議仿真的概念將環(huán)境視為在和敵手A運行協(xié)議π的進程與和敵手S運行協(xié)議φ的進程之間的“交互識別”。如果從任何環(huán)境的角度來看，對于協(xié)議π仿真協(xié)議φ，如果沒有環(huán)境可以判斷它是否與π和一些(已知的)敵手或與φ和其他一些敵手進行交互，那么協(xié)議π與φ一樣好。令REALπ,A,Z(k,z)和IDEALF,S,Z(k,z)表示現(xiàn)實模型和理想模型下環(huán)境機Z的輸出，其中k是安全參數(shù)，z是環(huán)境機Z的輸入。

定義1[21]兩個二元概率分布集合X和Y是不可區(qū)分的，記作X≈Y，如果對于任何c,d∈N存在k0∈N，對于所有k>k0和所有z∈Uκ≤kd{0,1}κ有：

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

定義2[21]如果對于任何現(xiàn)實攻擊者A，都存在一個理想攻擊者S，對于任何環(huán)境機Z，等式REALπ,A,Z(k,z)≈IDEALF,S,Z(k,z)恒成立，則稱協(xié)議πUC-實現(xiàn)了理想函數(shù)F，也稱協(xié)議π是UC安全的。即在k是安全參數(shù)且z是環(huán)境機Z的輸入的情況下，Z與A和π的各方運行交互之后輸出1的概率同Z與S和F交互之后輸出1的概率的不同可以忽略不計。

定理1[21]設(shè)π是F-混合協(xié)議，協(xié)議ρUC-實現(xiàn)理想函數(shù)F，則協(xié)議πρ/FUC-仿真協(xié)議π。

1.2 無證書簽密協(xié)議

定義3[12]一個無證書的簽密方案是由系統(tǒng)初始化、部分密鑰生成、私鑰生成、簽密算法和解簽密算法五個多項式時間算法組成。該方案的合法參與者有簽密者P、簽密消息接受者R和密鑰生成中心PKG。

1) 系統(tǒng)初始化(Setup)：PKG輸入安全參數(shù)1λ，生成輸出主密鑰s和系統(tǒng)參數(shù)params，保密s，公開params。

2) 部分密鑰生成(PartialKey.Extract)：PKG將需要產(chǎn)生部分密鑰的用戶P的身份IDp、params和s輸入，輸出P的部分私鑰PSp和部分公鑰PPp。

3) 私鑰生成(PrivateKey.Extract)：用戶P將params、IDp、PSp和隨機選取的秘密值sp輸入，輸出用戶私鑰SKp及公鑰PKp。

4) 簽密算法(SignCrypt)：簽密者P輸入params、待簽密消息m、簽密者的IDp及其私鑰SKp和接受者身份IDr及其公鑰PKr，輸出密文σ。

2 無證書簽密的理想函數(shù)FCLSC

FCLSC和簽密者P、接收者R、密鑰生成中心PKG及敵手A一起運行過程執(zhí)行如下。

1)Setup：當(dāng)收到PKG消息(Setup,sid)后，發(fā)送(Setup,sid,PKG)給敵手A；當(dāng)從A收到(Setup,sid,PKs)，輸出(Setup,sid,PKs)給PKG，記錄(PKG,PKs)。

2)PartialKey.Extract：當(dāng)從P收到第一個消息(PartialKey.Extract,sid),驗證sid是否等于(P,sid′),則發(fā)送(PartialKey.Extract,sid,IDp)發(fā)送給敵手A。將從A收到的(PartialKey.Received,sid,PKG,IDp)轉(zhuǎn)發(fā)給用戶P。

3)PrivateKey.Extract：當(dāng)收到用戶P的簽名密鑰生成請求(PrivateKey.Extract,sid)時，將(PrivateKey.Extract,sid,IDp)發(fā)給A。當(dāng)從A收到(PrivateKey.Received,sid,PKG,IDp,up,vp)時(vp是一個確定性多項式算法的描述,up是一個非確定性多項式算法的描述)，記錄(P,up,vp)并輸出(PrivateKey.Received,sid,IDp,vp)給用戶P。

4)SignCrypt：當(dāng)收到簽名者P發(fā)送的簽密請求(SignCrypt,sid,IDp,IDr,m)，驗證sid的有效性，并檢查(P,up)是否已經(jīng)記錄。如果被記錄，則向R輸出錯誤并停機；否則將(SignCrypt,sid,IDp,IDr)發(fā)給A，并計算σ=vp(m),記錄(m,σ,up),輸出(Ciphertext,sid,IDp,IDr,σ)給R。

3 無證書簽密協(xié)議的安全模型

3.1 基于IND-CCA2的安全性

定義4如果對于任何多項式時間的敵手，能夠以一個可忽略的概率贏得以下游戲，則稱一個無證書簽密方案在適應(yīng)性選擇密文攻擊下具有不可區(qū)分性(IND-CCA2)。

IND-CCA2游戲是由攻擊者A和挑戰(zhàn)者B共同完成。

1) 挑戰(zhàn)者B選取安全參數(shù)λ進行系統(tǒng)初始化Setup，將系統(tǒng)參數(shù)params給攻擊者A。

2) 初始化。攻擊者A執(zhí)行下述操作：

(1)PartialKey.Extract詢問：攻擊者A選擇一個身份IDv給挑戰(zhàn)者B，B計算PartialKey.Extract(params,s,IDv)→(PSv,PPv)，并發(fā)給A；

(2)PrivateKey.Extract詢問：攻擊者A選擇一個身份IDv和秘密值sv給挑戰(zhàn)者B，B計算PrivateKey.Extract(params,IDv,PSv,sv)→SKv，并發(fā)送給A。

3) 訓(xùn)練階段Ⅰ。

(1)SignCrypt詢問：攻擊者A選擇兩個身份IDv、IDr和消息m，挑戰(zhàn)者B對IDv進行私鑰生成詢問，對IDr進行公鑰生成詢問，計算σ=SignCrypt(SKv,PKr,m)并將σ發(fā)給A。

(2)UnSignCrypt詢問：攻擊者A選擇兩個身份IDv、IDr和密文σ，挑戰(zhàn)者B對IDr進行私鑰生成詢問，對IDv進行公鑰生成詢問，計算m′=UnSignCrypt(PKv,SKr,σ)并將此結(jié)果發(fā)給A。

4) 挑戰(zhàn)。攻擊者A輸出兩個長度相同的消息m0、m1及兩個挑戰(zhàn)身份IDv、IDr，其中IDr不能在之前的初始化和訓(xùn)練階段出現(xiàn)過，挑戰(zhàn)者B隨機選擇i∈{0,1}，計算σ=SignCrypt(SKv,PKr,mi)并將結(jié)果發(fā)給A。

5) 訓(xùn)練階段Ⅱ。過程與訓(xùn)練階段Ⅰ一樣，執(zhí)行多項式有界次詢問，但是不能對IDr執(zhí)行前面初始化和訓(xùn)練階段的各種詢問。另外，不能對挑戰(zhàn)中的簽密σ進行UnSignCrypt詢問。

(6) 猜測。攻擊者A輸出一個數(shù)值i′,如果i′=i,則攻擊者A攻擊成功,即贏得游戲。

3.2 UC框架下的無證書簽密協(xié)議πCLSC

UC框架下的無證書簽密協(xié)議由五個算法組成，即πCLSC=(Setup,PartialKey.Extract,PrivateKey.Extract,SignCrypt,UnsignCrypt)，協(xié)議的執(zhí)行步驟如下：

1) 收到輸入(Setup,PKG,sid)后，PKG運行Setup(1λ)→(params,s)，輸出相應(yīng)的參數(shù)params。

2) 收到輸入(PartialKey.Extract,sid)后,PKG先驗證sid=(sid′,PKG),再運行PartialKey.Extract(params,s,IDp)→(PSp,PPp)，輸出(Partial.Received,sid,IDp)。

3) 收到輸入(Partial.Received,sid,IDp)后，P運行PrivateKey.Extract(params,IDp,PSp,sp)→SKp。算法vp是簽密算法SignCrypt(SKp,·),算法up是驗證算法UnSignCrypt(PKp,·)。P輸出(PrivateKey.Received,sid,IDp,vp)。如果P從敵手A處得到一個“corruption”的請求，把簽名算法vp(·)輸出給敵手A。

4) 收到輸入(SignCrypt,sid,IDp,IDr,m)后，發(fā)送方P運行簽密算法σ=vp(m)，輸出(Ciphertext,sid,IDp,IDr,σ)。

5) 收到輸入(UnSignCrypt,sid,m,IDp,IDr,σ,up)后，驗證者計算f=UnSignCrypt(PKp,m,σ)，并輸出(UnSignCrypt,sid,m,IDp,IDr,σ,f)。

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

為了證明協(xié)議πCLSC在UC框架下可實現(xiàn)理想函數(shù)FCLSC，本文在理想模型中構(gòu)造一個理想的敵手，使得環(huán)境不能區(qū)分是現(xiàn)實模型中的執(zhí)行還是理想模型中的執(zhí)行。

定理2設(shè)CLSC是無證書的簽密方案，協(xié)議πCLSC安全實現(xiàn)理想函數(shù)FCLSC，當(dāng)且僅當(dāng)CLSC是IND-CCA2安全的。

必要性證明：假設(shè)協(xié)議πCLSC安全實現(xiàn)了理想函數(shù)FCLSC，那么對于任何環(huán)境Z都不可能區(qū)分它是在與理想?yún)f(xié)議FCLSC和理想環(huán)境中的敵手即仿真敵手S交互還是在與現(xiàn)實協(xié)議πCLSC和現(xiàn)實環(huán)境中的敵手A交互。因此CLSC滿足IND-CCA2安全性，即沒有敵手能夠以不可忽略的概率贏得IND-CCA2游戲。

首先構(gòu)造與理想函數(shù)FCLSC交互的理想敵手S，S執(zhí)行如下的操作：模擬理想函數(shù)FCLSC及模擬與環(huán)境的通信。

(1) 系統(tǒng)初始化：在收到FCLSC的消息(Setup,sid,PKG)后,運行參數(shù)生成算法Setup(1λ)→(params,s)，并返回相應(yīng)的(params,PKs)。

(2) 部分密鑰生成：在收到FCLSC的消息(PartialKey.Extact,sid,PKG,IDp)后，運行部分密鑰生成算法PartialKey.Extract(params,s,IDp)→(PSp,PPp)，產(chǎn)生(PSp,PPp)，返回PPp。

(3) 私鑰生成：在收到FCLSC的消息(PrivateKey.Extract,sid,IDp)后，運行私鑰生成算法Private.Extract(params,IDp,PSp,sp)→SKp，產(chǎn)生SKp，返回PKp。

(4) 簽密：在收到FCLSC的消息(SignCrypt,sid,IDp,IDr)后，如果消息發(fā)送者P未腐敗，則返回SignCrypt(paramas,m,IDp,IDr,SKp,PKr)→σ，并記錄(m,σ)；否則接收(SignCrypt,sid,m)，并返回(SignCrypt,sid,m,σ)。

(5) 解簽密：在收到FCLSC的消息(UnSignCrypt,sid,σ)后，返回UnSignCrypt(params,σ,IDs,IDr,SKr,PKs)→m，發(fā)送(m,f=0)給所有參與方；否則，將(m,f=1)發(fā)送給參與方。

下面證明仿真敵手S模擬了敵手A，構(gòu)造游戲IND-CCA2中的敵手A′：

挑戰(zhàn)者B產(chǎn)生系統(tǒng)參數(shù)params后，激活敵手A′。

① 在收到A′輸入(Setup,sid)后，B輸出sid=(sid,params)回應(yīng)。

② 在收到A′輸入(PartialKey.Extract,sid)后，(PartialKey.Extract,sid)請求時，B輸出(PSp,PPp)回應(yīng)。

③ 在收到A′輸入(PrivateKey.Extract,sid,IDv)后，向B發(fā)出(PrivateKey.Extract,sid,IDp)請求時，B輸出(SKp,PKp)回應(yīng)。

④ 在收到A′輸入(SignCrypt,sid,IDp,IDr,m)后，向B發(fā)出(SignCrypt,sid,m)請求時，B運行SignCrypt(sid,IDp,IDr,m),并返回σ。

⑤ 在收到A′輸入(UnSignCrypt,sid,m,IDp,IDr,σ)后，運行UnSignCrypt(params,m,σ)→f并返回f。當(dāng)f=1時，簽密成功；否則是偽造消息的簽密或者是由敵手來決定簽密是否有效。

根據(jù)上述對理想敵手S的描述，可以看出，在理想模型在執(zhí)行時，對于偽造簽名的驗證結(jié)果總是輸出0，因為不存在(sid,m,*,up,1)；而現(xiàn)實模型在執(zhí)行時，如果偽造簽密是成功的，則輸出的結(jié)果是1。

充分性證明：反證法。

假設(shè)CLSC是IND-CCA2的，那么協(xié)議πCLSC不能安全實現(xiàn)理想函數(shù)FCLSC，即環(huán)境機Z能區(qū)分它是與理想環(huán)境下的FCLSC和S交互還是與現(xiàn)實環(huán)境下的πCLSC和D(Dummy adversary)交互。用環(huán)境機Z構(gòu)造一個敵手B偽造出有效無證書簽密。

與敵手B進行如下交互：B可以調(diào)用環(huán)境機Z。

① 當(dāng)Z用輸入(Setup,sid)激活參與者P，如果P是“corrupted”，將結(jié)果(params,s)返回給Z。

② 當(dāng)Z用輸入(PartialKey.Extract,sid)激活參與方P，B將結(jié)果(PSp,PPp)返回給P。如果P是“corrupted”，則將(PSp,PPp)返回給Z。

③ 當(dāng)Z用輸入(SetSecret.Value,sid)激活參與方P,將結(jié)果(sp,PKp)返回給Z。

④ 當(dāng)Z用輸入(PrivateKey.Extract,sid,IDp)激活參與方P,B將結(jié)果(SKp,vp)返回給P。如果P是“corrupted”,B將結(jié)果(SKp,vp)返回給Z。

⑤ 當(dāng)Z用輸入(SignCrypt,sid,IDp,IDr,m)激活發(fā)送方P，B將得到的簽名σ返回給P。

⑥ 當(dāng)Z用輸入(UnSignCrypt,sid,m,IDp,IDr,σ,up)激活參與者P時，B令f=UnSignCrypt(PKp,m,σ)，輸出(UnSignCrypt,sid,m,σ,f)給P。

敵手B成功的概率分析如下：如果環(huán)境機Z是在與現(xiàn)實環(huán)境中的協(xié)議πCLSC和敵手A交互，因為簽密σ是有效的，所以Z將輸出1；如果環(huán)境機Z是在與理想模型中的理想函數(shù)FCLSC和模擬敵手S交互，因為不存在(sid,m,*,up,1)所以對于偽造簽密的驗證結(jié)果Z總是輸出0。證畢。

5 實例及性能分析

5.1 協(xié)議實例

3) 私鑰生成。當(dāng)收到(PrivateKey.Extract,sid,IDi)，IDi計算公鑰PKi=(Xi,Yi),私鑰為SKi=(xi,yi)。

5.2 性能分析

表1 開銷的對比

注:√表示方案具有該屬性，×表示方案不具有該屬性。

可以看出，文獻[12-14]的計算開銷與本文方案的差不多，而文獻[25-27]計算開銷就比本文方案大得多，但是文獻中的方案都不具有通用可組合性；在通信開銷方面本文方案和文獻[10-12]的相同，文獻[25-27]方案的消息長度較大，導(dǎo)致通信中的傳輸開銷比較大。與現(xiàn)有的無證書簽密方案相比，本文方案在計算開銷和通信效率方面都有一定的優(yōu)勢；另外，由于本文方案具有通用可組合性，與任意一組協(xié)議組成安全協(xié)議或者是作為任意系統(tǒng)的一個組成部分使用時，也能保證安全。

6 結(jié) 語

本文研究了無證書簽密方案的通用可組合安全性，給出了無證書簽密的形式化定義，定義了無證書簽密方案的理想函數(shù)，設(shè)計了滿足UC安全性的無證書簽密協(xié)議，證明了通用可組合的無證書簽密協(xié)議安全性與IND-CCA2安全性之間的等價關(guān)系，并基于離散對數(shù)問題給出了一個具體的通用可組合的無證書簽密實例。