標準模型下基于身份第三方受約束匿名加密方案*

明 洋，韓 娟，張 琳，周 俊

(長安大學信息工程學院，陜西 西安 710064)

1 引言

基于身份加密IBE(Identity-Based Encryption)的概念由Shamir A[1]于1984年首次提出，減輕了用戶對公鑰證書的需要。2001年,Boneh D等[2]提出第一個實用的IBE方案,之后提出了大量基于身份的加密方案[3～6]。

實際應用中IBE體制存在的內在問題是密鑰托管問題,目前主要有三種方案來解決該問題：(1)多PKG(Private Key Generator)方案[2]，用戶的私鑰由多個PKG共同生成，但多PKG的存在使得系統更復雜，通信代價大大增加；(2)無證書公鑰密碼CL-PKE(CertificateLess Public-Key Encryption)方案[7]，用戶的私鑰分別由PKG和用戶生成的兩個部分組成，但是該方案仍然存在一個可信的第三方來計算用戶的部分私鑰;(3)第三方權利受約束的IBE方案A-IBE(Accountable Authority IBE)方案。

2007年，Goyal V[8]提出A-IBE方案，通過修改用戶私鑰的生成方式減少用戶對PKG的信任需求；2010年，徐鵬等人[9]在Goyal方案基礎上，基于離散對數問題，提出一種標準模型下安全的通用A-IBE方案，該方案實現緊密安全歸約，但增加了系統參數和通信量；2011年，曹丹等人[10]基于Diffie-Hellman假設，提出安全有效的A-IBE方案；2012年，張方國等人[11]基于TBDHE(Decision Truncated Bilinear Diffie-Hellman Exponent)假設，提出一個弱的黑盒A-IBE方案，在標準模型下說明該方案是CCA2安全的，且具有緊密歸約。

應用中IBE體制常需要考慮匿名性問題，匿名性要求由密文不能得到接收者的身份。2006年Boyen X等人[12]提出一個標準模型下安全的匿名IBE方案；2010年，Liu L等人[13]對Boyen X等人[12]的方案進行改進，但沒有進行安全性證明；2012年，任艷麗等人[14]基于DBDH(Decisional Bilinear Diffie-Hellman)假設，利用階為合數的雙線性群，提出新的匿名IBE方案，在標準模型下可證安全。

針對IBE中的匿名性和密鑰托管問題，本文結合文獻[9,14]的思想，提出一個第三方權力受約束的匿名IBE方案，并基于DBDH假設和DL(Discrete Logarithm)假設在標準模型中證明方案的安全性，所提方案不僅可以保護接收者的隱私，同時也解決了密鑰托管問題。

2 預備知識

2.1 合數階雙線性群

設p、p′是兩個大素數，n=pp′，G、GT是兩個階為n的循環群，g是G的生成元。如果e:G×G→GT是一個雙線性映射,滿足以下性質：

(1)雙線性：e(ga,gb)=e(g,g)ab，對所有a,b∈Zn均成立。

(2)非退化性：?P,Q∈G，滿足e(P,Q)≠1。

(3)可計算性：存在有效算法計算e。

本文中，使用Gp、Gp′分別代表G中階為p、p′的子群，GT,p、GT,p′代表GT中的階為p、p′的子群，而且G=Gp×Gp′，GT=GT,p×GT,p′。如果g是G中的一個生成元，則gp′、gp分別是Gp、Gp′中的生成元，使用gp、gp′分別代表Gp、Gp′的生成元。

2.2 困難性問題

DBDH假設：如果t時間內沒有敵手能夠以至少ε優勢解DBDH問題，則DBDH問題是(t,ε)困難的。

(2)離散對數問題(DL)：令群Gp的階為p，g為生成元，給定ga，a∈Zp，計算a。

DL假設：如果t時間內沒有敵手能夠以至少ε優勢解DL問題，則DL問題是(t,ε)困難的。

2.3 通用A-IBE形式化定義

通用A-IBE方案由五個算法組成，定義如下：

(1)系統建立：輸入安全參數k，選定IBE方案I={系統建立，私鑰生成，加密，解密}，隨機生成系統公開參數PK={PK-I,PK-A}和私鑰SK={SK-I,SK-A}，其中PK-I和SK-I分別為方案I的系統公開參數和私鑰。

(2)私鑰生成協議：輸入身份信息ID和系統公開參數PK，PKG和用戶通過運行該協議，生成用戶私鑰dID={dI,dA}。

(3)加密：輸入身份信息ID，系統公開參數PK和明文M，在明文空間中隨機選取M1、M2，使得M=M1⊕M2,輸出密文C={C1,C2},其中，C1是M1的密文，C2是M2的密文。

(4)解密：輸入用戶私鑰dID={dI,dA}，系統公開參數PK和密文C={C1,C2}，輸出明文M=M1⊕M2，其中，M1是C1的明文，M2是C2的明文。

(5)跟蹤：取用戶私鑰dID作為輸入，輸出該私鑰的特征信息。

2.4 通用A-IBE安全模型

定義1如果t時間內沒有敵手能夠以至少ε優勢贏得以下三個游戲，則本文所提方案是安全的。

游戲1匿名性：通過挑戰者C和敵手A之間的交互游戲進行,具體如下：

系統建立:C執行系統建立算法，并把系統公開參數PK發送給A。

階段1 A適應性地進行下列詢問：

(1)私鑰詢問:C對身份ID執行私鑰詢問，并把對應的私鑰發送給敵手。

(2)解密詢問:C首先對身份ID執行私鑰詢問，然后用生成的私鑰解密密文C，并把明文M或出錯信息發送給A。

挑戰:A提交身份ID0、ID1和消息M0、M1給C,其中ID0、ID1均沒有在詢問階段1中執行過私鑰詢問，C隨機選擇β,γ∈{0,1}，計算密文C*=Encrypt(PK,IDβ,Mγ)，并把C*發送給A。

階段2A繼續適應性地進行詢問，但是不能對ID0、ID1進行私鑰詢問，對〈ID0,C*〉和〈ID1,C*〉進行解密詢問。

猜測：A輸出對β、γ的猜測β′、γ′∈{0,1}，如果β′=β,γ′=γ，A贏得游戲。

稱A為ANON-IND-ID-CCA2敵手，其優勢定義為|Pr[β′=β∧γ′=γ]|-1/4。

在上述游戲中，如果敵手不能進行解密詢問，則被稱為ANON-IND-ID-CPA敵手。

定義2如果t時間內沒有ANON-IND-ID-CPA敵手在經過q次私鑰詢問后，能夠以至少ε優勢贏得上述游戲，則所提方案是(t,q,ε)-ANON-IND-ID-CPA安全的。

游戲2TheFindKeygame：通過挑戰者C和敵手A之間的交互游戲進行，具體如下：

系統建立：敵手A(即敵對的PKG)產生系統公開參數，并將系統公開參數及身份ID發送給挑戰者C；挑戰者C對系統公開參數進行有效性檢測，若檢測失敗，游戲中止。

私鑰生成：敵手A和挑戰者C通過運行私鑰生成協議，挑戰者C生成身份ID的私鑰dID并輸出，并對其進行有效性檢測，若檢測失敗，游戲中止。

游戲3TheComputerNewKeygame：通過挑戰者C和敵手A之間的交互游戲進行，具體如下：

系統建立：挑戰者C運行系統建立算法，并將系統公開參數發送給敵手A。

私鑰生成:敵手A適應性地查詢任意用戶的私鑰，挑戰者C將對應的私鑰發送給A。

2.5 1/n不經意傳輸

不經意傳輸[15]是指允許接收者從發送者所給的n個秘密中選取一個，且發送者無法知道接收者選擇了哪一個，同時接收者也無法知道其他的秘密。

3 第三方權力受約束的匿名IBE方案

系統建立：

PK=(gp′,G,G′,U,e(g1,g2),gy,PK-A)

私鑰為:

SK=(g1,g2,u′,u,y,SK-A)

私鑰生成協議：

(2)對任意i∈SID，當IDi=0時，PKG從矩陣SK-A中選取元素tx,i=th,i，計算并返回ri/th,i給用戶；當IDi=1，PKG從矩陣SK-A中選取元素tx,i=t1,i，計算并返回ri/t1,i給用戶。

(4)用戶計算dA=({ri/tx,i}i∈SID,{ki,ri/tki,i}i∈Ssp)，并檢驗:

若等式不成立，則用戶退出。

(5)用戶將dID=(dI,dA)作為私鑰。

加密：

解密：

給定密文C=(CI,CA)，

(2)對CA解密之前，首先進行密文有效性檢驗，即:

若等式成立，計算:

(3)輸出M=M1·M2。

跟蹤：

取私鑰dID作為輸入，該確定算法輸出Trace(dID)=klID+1‖…‖kl，即私鑰特征值為所有的ki串聯。

4 方案的安全性證明

定理1(匿名性) 假定(t′,ε′,q)-DBDH在G,GT中成立，那么所提方案是(t,ε,q)-ANON-IND-ID-CPA安全的,其中:

t′=t+O(ε-2ln(ε-1)λ-1ln(λ-1))

證明假定敵手A存在，構建算法B解決DBDH問題，即給定ga、gb、gc∈Gp，判斷Z=e(g,g)abc是否成立。

系統建立：

算法B計算m=4q，并隨機選擇k∈{0,1,…,lID}，x′∈{0,1,…,m-1}，一個lID比特向量x=(xi)，其中xi∈{0,1,…,m-1}，B隨機選擇y′∈Zn及一個lID比特向量y=(yi)，其中yi∈Zn。

PK=(G,G′,U,e(g1,g2),gy,PK-A)

其中:

私鑰為:

SK=(g1,g2,u′,u,y,SK-A)

其中:

階段1

敵手適應性地對任意身份信息ID進行私鑰詢問，算法B運行I的私鑰生成算法，如果K(ID)=0，B放棄并隨機選擇ω′，否則，隨機選擇r∈Zn，計算

挑戰：

A提交身份ID0、ID1和消息m0、m1給B，且ID0、ID1均未在階段1中進行私鑰詢問。

令t*=c，如果Z=e(g,g)abc，則

階段2

A繼續進行適應性的私鑰詢問，但不能對身份ID0、ID1進行私鑰詢問。

猜測：

A輸出對β、γ∈{0,1}的猜測β′、γ′∈{0,1}，如果β=β′,γ=γ′，則敵手贏得游戲。

□

系統建立：

敵手A(即敵對的PKG)產生系統公開參數為:

PK=(G,G′,U,e(g1,g2),gy,PK-A)

并將PK及身份ID發送給B，算法B對PK進行有效性檢測，若檢測失敗，算法B中止。

私鑰生成：

算法B與敵手A共同運行私鑰生成協議，算法B生成身份ID的私鑰dID并輸出，并對其進行有效性檢測，若檢測失敗，算法B中止。

私鑰尋找：

□

定理3假設DL假設成立，則在安全性ComputerNewKeygame定義下，敵手攻破A-IBE方案的優勢可忽略。

系統建立：

算法B運行方案的系統建立算法，生成系統公開參數為:

PK=(G,G′,U,e(g1,g2),gy,PK-A)

私鑰為：

SK=(g1,g2,u′,u,y,SK-A)

其中,

并將PK發送給敵手A。

私鑰詢問：

該階段敵手A通過與算法B運行私鑰生成協議，詢問到任意用戶的私鑰。對于敵手A詢問的任意身份信息ID,算法B的處理過程如下：

(2)對任意i∈SID，當IDi=0時，算法B計算并返回ri/th,i給A；當IDi=1，算法B計算并返回ri/t1,i給A。

(4)敵手A得到:

dA=({ri/tx,i}i∈SID,{ki,ri/tki,i}i∈Ssp-{l},

{kl,rl/tkl,l:kl≠h},{kl,rl:kl=h})

并進行檢驗，如果kl≠h，則dA總能通過檢測；如果kl=h，則僅在a=1時可通過檢測，而由于a=1的概率可忽略，因此此時dA幾乎不能通過檢測。

(5)若dA未能通過私鑰有效性檢測，則算法B中止，否則敵手A得到身份ID的私鑰dID={dI,dA}。

新私鑰生成：

□

5 性能分析比較

由表1可以看出，本文方案和文獻[9,14]比較，在標準模型下的Adaptive-ID模型中可證安全;在運算次數方面,和文獻[9]相比，次數相同，而且具有匿名性。因此，所提方案不僅實現了匿名性，同時解決了密鑰托管問題，具有較高的安全性和效率。

6 結束語

鑒于IBE方案中存在的匿名性和密鑰托管問題，本文基于DBDH假設和DL假設，使用階為合數的雙線性群，提出一個第三方權力受約束的匿名IBE方案，實現了IBE中接收者的匿名性，且解決了密鑰托管問題。

近幾年來，這一領域的研究工作主要是實現弱的黑盒A-IBE方案或完全有效的黑盒型A-IBE方案[16～20]，具有較高的安全性和緊密的規約性，并實現了公開的追蹤，從而找到不誠實的PKG或用戶。所以，后續工作是對文中方案進行改進，實現黑盒型的匿名A-IBE方案，并在標準模型下可證安全。

Table 1 Performance comparison of schemes

注*，l是關于k的安全多項式

[1] Shamir A.Identity-based cryptosystems and signature scheme[C]∥Proc of Cryptology-CRYPTO’84,1984:47-53.

[2] Boneh D,Franklin M.Identity-based encryption from the weil pairing[C]∥Cryptology-CRYPTO’01,2001:213-229.

[3] Boneh D,Boyen X.Efficient selective-ID identity-based encryption without random oracles[C]∥Proc of Cryptology-EUROCRYPT’04,2004:223-238.

[4] Boneh D,Boyen X.Secure identity-based encryption without random oracles[C]∥Proc of Cryptology-CRYPTO’04,2004:443- 459.

[5] Waters B.Efficient identity-based encryption without random oracles[C]∥Proc of Cryptology-EUROCRYPT’05,2005:114-127.

[6] Gentry C.Practical identity-based encryption without random oracles[C]∥Proc of Cryptology-EUROCRYPT’05,2005:445-464.

[7] Al-Riyami S,Paterson K.Certificateless public key Cryptography[C]∥Proc of Cryptology-ASIACRYPT’03,2003:452-473.

[8] Goyal V.Reducing trust in the PKG in identity-based cryptosystems[C]∥Proc of Cryptology-CRYPTO’07,2007:430-447.

[9] Xu Peng,Cui Guo-hua,Fu Cai,et al. A more efficient reducing trust in the PKG IBE scheme under DL assumption[J].Journal of Science China(Information Science),2010,40(2):285-297.(in Chinese)

[10] Cao Dan,Wang Xiao-feng,Wang Fei. A secure and accountable identity-based encryption scheme[J]. Journal of Electronics & Information Technology, 2011,33(12):2922-2928.(in Chinese)

[11] Zhao Xing-wen,Zhang Fang-guo.Fully CCA2 secure identity-based broadcast encryption with black-box accountable authority[J].Journal of Systems and Software, 2012,85(3):708-716.

[12] Boyen X,Waters B.Anonymous hierarchical identity-based encryption without random oracles[C]∥Proc of Cryptology -CRYPTO’06,2006:290-307.

[13] Liu L,Cao Z.Improvements of one anonymous ID-based encryption[C]∥Proc of ICETC’2010,2010:256-260.

[14] Ren Yan-li,Gu Da-wu,Wang Shuo-zhong, et al.Anonymous identity-based encryption sheme without random oracles[J].Journal of University of Science and Technology of China,2012,42(4):296-301.(in Chinese)

[15] Tzeng W G.Efficient 1-out-of-noblivious transfer with universally usable parameters[J].IEEE Transactions on Computers,2004,53(2):232-240.

[16] Goyal V,Steve L,Sahai A,et al.Black-box accountable authority identity-based encryption[C]∥ Proc of ACM Conference on Computer and Communications Security, 2008:427-436 .

[17] Libert B,Vergnaud D.Towards black-box accountable authority IBE with short ciphertexts and private keys[C]∥Proc of PKC’09,2009:235-255.

[18] Libert B,Vergnaud D.Towards practical black-box accountable authority IBE:Weak black-box traceability with short ciphertexts and private keys[J]. IEEE Transactions on Information Theory, 2011,57(10):7189-7204.

[19] Sahai A,Seyalioglu H.Fully secure accountable-authority identity-based encryption[C]∥Proc of PKC 2011,2011:296-316.

[20] Lai Jun-zuo,Deng R,Zhao Yun-lei,et al. Accountable authority identity-based encryption with public traceability[C]∥Proc of Cryptology-CRYPTO’13,2013:326-342.

附中文參考文獻：

[9] 徐鵬，崔國華，付才，等.DL假設下一種更高效的第三方權力受約束的IBE方案[J].中國科學(信息科學)，2010,40(2):285-297.

[10] 曹丹，王小峰，王飛.一種安全可追責的基于身份加密方案[J].電子與信息學報，2011,33(12):2922-2928.

[14] 任艷麗，谷大武，王朔中，等.標準模型中基于身份的匿名加密方案[J].中國科學技術大學學報，2012,42(4):296-301.