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

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

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

1 引言

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

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

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

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

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

2 相關數學基礎知識

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

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

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

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

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

假設G1是由生成元 P 生成的循環群，其階為素數q，令G2代表另一個階也是q的循環群。令群G1與G2上的離散對數難題假設成立。

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

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

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

3)可計算：如果P,Q∈G1，則 e(P,Q)∈G2是可在多項式時間內計算的。

3 提出的新方案

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

3.1 第1個新方案

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

系統初始化(Setup)：給定安全參數 k，進行以下步驟計算。

1)輸出 2個階為素數q的循環群G1與G2、群G1的生成元P，以及雙線性映射 e: G1×G1→G2。

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

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

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

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

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

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

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

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

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

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

3.2 第2個新方案

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

系統初始化(Setup): 給定一個安全參數k，執行下面的步驟。

1)輸出2個階為素數q的循環群G1與G2、群G1的生成元P，以及雙線性映射 e: G1×G1→G2。

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

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

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

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

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

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

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

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

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

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

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

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

3.3 效率和實用性

通過表1來說明本文所提出方案的高計算效率和強實用性。

表1 E-PKE方案間的比較

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

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

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

3.4 第2個方案的可證明安全性

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

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

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

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

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

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

證明 假設敵手 A針對 H2最多定下q2次詢問，其成功優勢是ε。下面，詳細構造算法 B，它借助運行敵手A并與之進行交互來成功解決iBDH難題。

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

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

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

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

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

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

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

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

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

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

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

4 結束語

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

[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.