可證安全的高效可托管公鑰加密方案

劉文浩，王圣寶，曹珍富，韓立東

(1. 杭州師范大學(xué) 信息科學(xué)與工程學(xué)院，浙江 杭州 310012；2. 上海交通大學(xué) 計(jì)算機(jī)科學(xué)與工程系，上海 200240)

1 引言

N=1公鑰密碼學(xué)在網(wǎng)絡(luò)信息安全中的作用越來越受到人們重視，它能夠同時(shí)為用戶提供保密性和抗抵賴（數(shù)字簽名）服務(wù)[1]。然而，利用唯一一個(gè)公鑰/私鑰元組來同時(shí)提供這 2種服務(wù)的做法存在嚴(yán)重問題。首先，為了防止由于用戶私鑰的丟失而造成對先前密文的不可解密，或者出于法律監(jiān)管的需要，往往要求用戶將解密私鑰托管到可信任的托管中心(EA,escrow agency)。其次，對于數(shù)字簽名服務(wù)而言，出于滿足真正意義上的不可抵賴性的目的，又要求簽名私鑰應(yīng)該只能為簽名人所掌握，即托管中心不能夠獲得用戶的(簽名)私鑰。所以，當(dāng)使用傳統(tǒng)公鑰加密方案(例如RSA)時(shí)，由于解密私鑰與簽名私鑰相同，用戶的唯一私鑰是否被托管就是一個(gè)矛盾。

現(xiàn)行公鑰基礎(chǔ)設(shè)施(PKI,public key infrastructure)為了調(diào)和這個(gè)矛盾，一般采用“雙證書模式”[2]，即讓每個(gè)用戶使用2對公/私鑰。2個(gè)公鑰分別被2份公鑰證書所證實(shí)。然而，這種做法的最大問題在于它使得PKI 所頒發(fā)的證書數(shù)目加倍，極大增加了其證書管理負(fù)荷。并且，這種模式也增加了用戶端自身負(fù)擔(dān)：每個(gè)用戶必須存儲和管理2個(gè)私鑰，即解密私鑰和簽名私鑰。

2001年，Verheul[3]提出的可托管公鑰加密(E-PKE,escrowable public-key encryption)方案成功解決了上述難題。它的基本思想是，解密權(quán)能夠在不犧牲數(shù)字簽名服務(wù)的前提下被托管。在這種全新加密方案中，用戶的唯一公鑰對應(yīng)于2個(gè)解密私鑰：自己掌握的主解密私鑰(primary decryption key)，記為KP；可交給托管中心的托管解密私鑰(escrow decryption key)，記為KE。其中，主解密私鑰不能夠被托管中心利用托管解密私鑰計(jì)算出來。此時(shí)，用戶利用其主解密私鑰 KP進(jìn)行的數(shù)字簽名就滿足法律意義上的不可抵賴性。這種方案被分成如下2類。

1)主動方案：用戶能自主決定是否將托管解密私鑰 KE托管。顯然，如選擇托管，用戶需要通過安全信道首先將托管解密私鑰KE交付給托管中心。例如，Verheul[3]提出的第1個(gè)此類方案就是主動式方案。

2)被動方案：也稱為全局托管方案。用戶不能自主選擇是否將解密權(quán)托管。托管中心能依靠其唯一托管解密私鑰（也即系統(tǒng)主私鑰），解密系統(tǒng)中所有用戶的密文。Boneh 和 Franklin[4,5]提出的E-PKE方案就屬于被動式方案。

2 相關(guān)數(shù)學(xué)基礎(chǔ)知識

本文所討論的全部方案都基于雙線性映射(bilinear pairing)。因此，這里有必要首先回顧相關(guān)難題假設(shè)，然后給出雙線性映射的定義。

定義1 (離散對數(shù)難題(DLP,discrete logarithm problem))。假設(shè)(G,·)表示一個(gè)階為q的群，g 是它的生成元。離散對數(shù)難題是：給定隨機(jī)元素y∈RG，找到一個(gè)數(shù)x∈Zq，使得 y=gx。

定義2 (計(jì)算性 Diffie-Hellman 難題(CDHP,computational Diffie-Hellman problem))。假設(shè)(G,·)表示一個(gè)階為q的群，g表示它的生成元。計(jì)算性Diffie-Hellman難題是：給定一個(gè)隨機(jī)三元組(g,ga,gb)，其中，元素，計(jì)算 gab。

定義3 (判定性 Diffie-Hellman 難題(DDHP,decisional Diffie-Hellman problem))。假設(shè)(G,·)是一個(gè)階為q的群，g為其生成元。判定性 Diffie-Hellman 難題是：給定三元組(ga,gb,gc)，其中，隨機(jī)元素，判斷 gc=gab成立與否。

概略地說，離散對數(shù)(DL)、計(jì)算性 Diffie-Hellman (CDH)以及判定性Diffie-Hellman (DDH)假設(shè)指的是：不存在概率多項(xiàng)式時(shí)間算法能夠以不可忽略的優(yōu)勢解決DLP、CDHP 或DDHP 難題。

假設(shè)G1是由生成元 P 生成的循環(huán)群，其階為素?cái)?shù)q，令G2代表另一個(gè)階也是q的循環(huán)群。令群G1與G2上的離散對數(shù)難題假設(shè)成立。

定義4 (雙線性映射(Pairing))。雙線性映射e是雙線性函數(shù)e: G1×G1→G2，它符合以下性質(zhì)。

1)雙線性：如果P,Q∈G1并且，那么e(a P,b Q)=e(P,Q)ab。

2)非退化：滿足 e(P,P)=1。

3)可計(jì)算：如果P,Q∈G1，則 e(P,Q)∈G2是可在多項(xiàng)式時(shí)間內(nèi)計(jì)算的。

3 提出的新方案

這里給出本文新提出的2個(gè)可托管公鑰加密方案。值得特別指出的是，為了節(jié)省篇幅，省略了對可托管公鑰加密方案的形式化定義。相關(guān)定義與其他類別的公鑰加密方案極其類似，例如 Boneh 和Franklin[4,5]所給出的關(guān)于基于身份的加密方案的形式化定義。不同之處僅在于，可托管公鑰加密方案中用戶的私鑰有2個(gè)，相應(yīng)地，解密算法也有2個(gè)。

3.1 第1個(gè)新方案

本文第1個(gè)新方案來源于Boneh-Frankin[1,2]被動式方案。不同之處在于將它轉(zhuǎn)化為主動式方案。

系統(tǒng)初始化(Setup)：給定安全參數(shù) k，進(jìn)行以下步驟計(jì)算。

1)輸出 2個(gè)階為素?cái)?shù)q的循環(huán)群G1與G2、群G1的生成元P，以及雙線性映射 e: G1×G1→G2。

2)選擇雜湊函數(shù)H: G →{0,1}n，其中，n是整數(shù)。此方案的明文空間是 M={0,1}n，密文空間是。系統(tǒng)公共參數(shù) params為(q,G1,G2,e,n,P,H)。

私鑰生成(Key-Gen)：每個(gè)用戶可按如下算法生成自己的公/私鑰元組。

1)隨機(jī)選擇 2個(gè)隨機(jī)數(shù) x1,x2∈Zq，并把其中任意一個(gè)設(shè)置為主解密私鑰，這里假定主解密私鑰KP=x1。

2)托管解密私鑰：KE=x2。

3)用戶公鑰為P1=x1P及 P2=x2P∈G1

加密算法(Encryption)：為了加密消息m∈M，加密方首先選擇 r∈Zq，把密文設(shè)為C=(r P,m⊕H(gr)),其中 g=e(P1,P2)∈。

解密算法(Decryption)：密文 C=(U,V)，利用自己的主解密私鑰x1計(jì)算 m=V ⊕ H(e(U,x1P2))。

托管解密(Escrow-Decrypt)：對于密文C=(U,V)，托管中心利用托管解密私鑰KE計(jì)算m=V ⊕H(e(U,KEP1))。

方案正確性：這個(gè)方案的加解密正確性基于如下事實(shí)，解密者和托管中心雙方都能正確地由密文C的前半部分U計(jì)算獲得加密方用于對明文m進(jìn)行加密的會話密鑰，即 e(U,x1P2)=gr。同樣，e(U,KEP1)=gr。

不同于一般意義上的可托管公鑰加密方案，這里用戶的唯一公鑰(由1P和2P雙元組組成)還對應(yīng)于另外1個(gè)解密私鑰——第3個(gè)解密私鑰x1x2P。用戶也可以把私鑰x1x2P作為托管解密私鑰交付給托管中心。如果這樣，用戶握有的兩對公/私鑰元組(x1,P1)和(x2,P2)都可以作為簽名私鑰/驗(yàn)證公鑰元組，用來提供抗抵賴服務(wù)。

3.2 第2個(gè)新方案

本文提出的第2個(gè)方案是主動式的可托管公鑰加密方案。它的基本過程描述如下。

系統(tǒng)初始化(Setup): 給定一個(gè)安全參數(shù)k，執(zhí)行下面的步驟。

1)輸出2個(gè)階為素?cái)?shù)q的循環(huán)群G1與G2、群G1的生成元P，以及雙線性映射 e: G1×G1→G2。

2)計(jì)算 g2=e(P,P)。

3)選擇雜湊函數(shù)H: G2→{0,1}n，其中n是整數(shù)。

此方案的明文空間是 M={0,1}n，密文空間是C=。系統(tǒng)公共參數(shù) params為(q,G,1G2,e,n,P,g2,H)。

私鑰生成(Key-Gen)：這是用戶的（雙）私鑰生成算法。每個(gè)用戶生成自己的公鑰及其對應(yīng)的2個(gè)解密私鑰。

1)首先，隨機(jī)選擇一個(gè)隨機(jī)數(shù)x∈Zq，并將其設(shè)置為主解密私鑰，即KP=x。

2)將托管解密私鑰設(shè)為KE=x-1P。

3)將公鑰設(shè)為PPub=xP∈G1。

加密算法(Encryption)：對消息m∈M進(jìn)行加密，加密方首先選擇 r∈Zq，接著計(jì)算得到密文：C=(r PPub,m ⊕ H(g2r)。

解密算法(Decryption)：收到密文 C=(U,V)，解密方利用KP進(jìn)行如下計(jì)算獲得明文：m=V ⊕ H2(e(U,KP-1P))。

托管解密算法(Escrow-Decrypt)：托管中心得到密文 C=(U,V )后，使用KE進(jìn)行如下計(jì)算獲得明文：m=V ⊕ H2(e(U,KE))。

4)方案的正確性：此方案的正確性源自于這一事實(shí)，無論是用戶自己（解密方）還是托管中心，都能夠通過密文C的前半部分U計(jì)算獲得加密方用于加密明文m的會話密鑰，即=e(U,KE)=g2r。

方案滿足主私鑰安全性：托管中心獲得的托管解密私鑰為KE=x-1P，而由用戶唯一掌握的主解密私鑰為KP=x，因此，從托管解密私鑰計(jì)算獲得主解密私鑰，等價(jià)于群G1上的離散對數(shù)難題。

3.3 效率和實(shí)用性

通過表1來說明本文所提出方案的高計(jì)算效率和強(qiáng)實(shí)用性。

表1 E-PKE方案間的比較

首先來分析加密方的計(jì)算效率。在本文所提出的第2個(gè)方案的加密過程中，加密方不需要計(jì)算任何雙線性映射，也即加密方無論是在線還是離線階段都無需進(jìn)行雙線性映射函數(shù)的計(jì)算。在現(xiàn)有的總共4個(gè)方案中，只有Verheul方案[3]也滿足這樣的高計(jì)算效率，而其他2個(gè)方案中的加密方都需要在線地（也即獲得了解密方的公鑰，或公鑰證書之后）計(jì)算一個(gè)雙線性映射。進(jìn)一步，第 2個(gè)方案比Verheul的方案更加實(shí)用，這是因?yàn)楸疚牡姆桨钢校用芊皆谝阅撤N方式獲得解密方的公鑰之前，就能夠首先利用系統(tǒng)公共參數(shù)計(jì)算得到用于加密明文消息的會話密鑰 g2r，其中r為加密方選擇的一個(gè)隨機(jī)整數(shù)（可離線選定并存儲備用）。這意味著明文可以被預(yù)先加密。換句話說，密文C的后半部分V可在離線階段提前得到計(jì)算。這大大提高了加密效率。而在Verheul方案中，要求加密方在獲得解密方的公鑰PPub之后，方能進(jìn)行會話密鑰的計(jì)算。其中，r也是加密方選擇的一個(gè)隨機(jī)整數(shù)（也可離線選定并存儲備用）。

而在其他方案方面，在Boneh-Frankin 方案和本文所提出的第1個(gè)方案中，加密方在加密時(shí)必須在線地（即獲得解密方的公鑰之后）完成雙線性映射的運(yùn)算。

其次，來看密鑰的長度。本文所提出的第2個(gè)方案中的用戶主解密私鑰的長度達(dá)到了最優(yōu)，即為Zq中一個(gè)整數(shù)的長度。而在公鑰的長度方面，Verheul 方案是群G2中的單個(gè)元素，相比而言，本文所提出的第2個(gè)方案中，其值為群G1中的單個(gè)元素。一般來說，后者的長度要短于前者。

3.4 第2個(gè)方案的可證明安全性

眾所周知，利用由日本學(xué)者Fujisaki 和Okamoto所提出的通用轉(zhuǎn)化方法[7]，能夠很方便地把達(dá)到選擇明文安全性的公鑰加密方案，增強(qiáng)為達(dá)到選擇密文安全性的方案。因此，這里只給出了方案的選擇明文安全性證明。由于本文所提出的第2個(gè)方案是全部現(xiàn)有同類方案中最為高效和實(shí)用的。因此，這里只給出對它的安全性證明。類似地，也能夠給出其他方案的安全性證明。

為了節(jié)約篇幅，省略了對可托管公鑰加密方案的形式化安全模型的描述。這一安全模型與傳統(tǒng)公鑰加密方案的形式化安全模型并無特殊差異。這主要是因?yàn)椋菏紫?，解密私鑰的增加并不會降低方案的安全性，換句話說，所有解密私鑰的總體可被看作傳統(tǒng)公鑰加密方案中的唯一私鑰，都是需要被嚴(yán)格保密的；其次，由于托管中心獲得了被托管的托管解密私鑰，因此它具有同等的解密能力。它不能被看作可能的敵手。

接下來，給出該方案選擇明文安全性所基于的難題假設(shè)：逆BDH (iBDH)難題假設(shè)。

定義5 逆Diffie-Hellman (iBDH)問題)。令群G1、G2、生成元P以及e與前文所定義的同名參數(shù)相同。(G1,G2,e)上的 iBDH問題為：假設(shè)有(P,a P,b P)，其中，隨機(jī)的元素，計(jì)算

非嚴(yán)格地說，逆 BDH (iBDH)難題假設(shè)即逆BDH (iBDH)難題是難解的，即不存在多項(xiàng)式時(shí)間算法能計(jì)算這一問題。值得指出的是，Zhang等人[8]給出了iBDH 難題假設(shè)與標(biāo)準(zhǔn)雙線性Diffie-Hellman(BDH)難題假設(shè)相互等價(jià)的證明。以下定理給出了第2個(gè)方案的選擇明文安全性。

定理1 假設(shè)存在一個(gè)優(yōu)勢為ε的敵手A，它是針對該方案的選擇明文攻擊敵手，假設(shè)它最多進(jìn)行q2次 H 詢問，則可構(gòu)造出一個(gè)算法 B，它能以不小于 2ε/q2的優(yōu)勢成功破解iBDH 難題。

證明 假設(shè)敵手 A針對 H2最多定下q2次詢問，其成功優(yōu)勢是ε。下面，詳細(xì)構(gòu)造算法 B，它借助運(yùn)行敵手A并與之進(jìn)行交互來成功解決iBDH難題。

假設(shè) B的初始輸入值為(q,G1,G2,e)和(P,aP,bP)。用來代表對應(yīng)于該難題輸入的iBDH 難題的解。

初始化：B將公鑰設(shè)定成(q,G1,G2,e,PPub,n,P,H )，其中，PPub=aP。敵手A 首先獲得公鑰。這里，未知的解密私鑰是 a-1P。后續(xù)證明過程中，H為B所完全掌握的隨機(jī)Oracle。

H-查詢：為了模擬敵手A對隨機(jī)OracleH的詢問，算法B維護(hù)一個(gè)列表(稱為H-表)，其格式為(Xj,Hj)。面對詢問X，算法B首先檢查它是否已經(jīng)存在于H-表之上。若存在，則算法B返回相應(yīng)記錄中的H值。否則，從{0,1}n中隨機(jī)選擇一個(gè)H值返送到敵手A，并把條目(X,H)添入H-表。

挑戰(zhàn)：當(dāng)上述第一階段結(jié)束后，敵手A輸出2個(gè)明文消息M0、M1，它們的長度相同。算法B隨機(jī)選擇t∈{0,1}和串 S∈{0,1}n，接著，把針對明文消息的加密 C*設(shè)定為C*=(U,V)，其中，U=bP，V=Mt⊕ S 。算法B將挑戰(zhàn)密文 C*傳遞給敵手A。

如前所述，a-1P是任何一方都未知的解密私鑰，D是算法B所面臨的iBDH問題的解。注意，對密文 C*進(jìn)行解密，得到的結(jié)果為V ⊕H(e(a-1P,bP))=V ⊕ H(D)。

猜測：敵手 A在獲得密文 C*后，仍然可以發(fā)起H-詢問。過后，敵手A輸出關(guān)于比特值t的猜測t∈{0,1}。

輸出：最后，算法B隨機(jī)地從H-表上摘下一個(gè)條目(Xj,Hj)并輸出其中的Xj作為它的 iBDH難題解。

顯然，算法B的上述模擬過程對于敵手來說是完美和不可區(qū)分的。因此，得出結(jié)論：敵手A的成功優(yōu)勢為ε。將H表示為如下事件：在算法B的模擬過程中，敵手 A以D作為輸入，詢問隨機(jī)OracleH。

由于H(D)的值是敵手A無法預(yù)測的，所以，如果它在沒有針對H詢問D，則它也無法預(yù)測挑戰(zhàn)密文 C*的解密輸出。因此有如下結(jié)論：在攻擊模擬游戲中 Pr[ t=t'|-H]-1/2。

依據(jù)關(guān)于敵手 A的定義，在真正的攻擊中(以及在針對它的模擬中)，|Pr[ t=t′|-H]-1/2|≥ε。關(guān)于 Pt[ t=t′]，可得到以下界值

因此有：|Pr[ t=t′]-1/2|≤Pr[ H ]/2。又由于|Pr[ t=t']-1/2|≥ε，因此有：Pr[ H]≥2ε。依據(jù)H的定義可推出D出現(xiàn)在H-表中的概率不小于2ε。進(jìn)一步，算法B求得正確的iBDH 難題實(shí)例解的概率不小于 2ε/q2，這與假設(shè)iBDH 問題是難解的假設(shè)矛盾。

4 結(jié)束語

可托管公鑰加密方案是一種具有很好應(yīng)用前景的新型加密方案。特別是隨著同樣利用雙線性映射所構(gòu)造的基于身份的加密方案被逐步應(yīng)用[9]，可托管公鑰加密有望成為解決現(xiàn)行公鑰基礎(chǔ)設(shè)施中證書管理負(fù)擔(dān)過重問題的一種有效解決方案。本文提出了2個(gè)新的此類方案。其中，第二個(gè)方案的加密過程最為高效，并且它允許加密方能夠以離線方式提前加密明文。最后，詳細(xì)給出了它的安全性證明。本文所給出的方案是在隨機(jī)預(yù)言模型中安全的，是否存在標(biāo)準(zhǔn)模型下安全的此類方案，值得進(jìn)一步研究。

[1]ZIMMERMANN P. Pretty Good Privacy―Public Key Encryption for the Masses,PGP User’s Guide[M]. Cambridge,MA: MIT Press,1995.

[2]SANTESSON S,POLK W,BARZIN P,et al. Internet X.509 Public Key Infrastructure,Qualified Certificates Profile,RFC 3039,IETF[S].2001.

[3]VERHEUL E R. Evidence that XTR is more secure than supersingular elliptic curve crypto systems[A]. Proc of Eurocrypt'01[C]. Springer,2001.195-210.

[4]BONEH D,FRANKLIN M. Identity-based encryption from the weil pairing[A]. Proc of CRYPTO'01[C]. Springer,2001.213-229.

[5]BONEH D,FRANKLIN M. Identity-based encryption from the weil pairing[J]. SIAM J Computing,2003,32(3):586-615.

[6]ELGAMAL T. A public key cryptosystem and signature scheme based on discrete logarithms[J]. IEEE Trans Inf Theory,1985,31(4):469-472,

[7]FUJISAKI E,OKAMOTO T. How to enhance the security of public-key encryption at minimum cost[J]. IEICE Trans Fundamentals,2000,9(1): 24-32.

[8]ZHANG F,SAFAVI-NAINI R,SUSILO W. An efficient signature scheme from bilinear pairings and its applications[A]. Proc of PKC'04[C]. Springer,2004.277-290.

[9]LYNN B. On the Implementation of Pairing-Based Cryptography[D].Stanford University,2006.