李順東,楊坤偉，鞏林明，毛　慶，劉　新

(陜西師范大學計算機科學學院，陜西西安 710119)

?

標準模型下可公開驗證的匿名IBE方案

李順東,楊坤偉，鞏林明，毛慶，劉新

(陜西師范大學計算機科學學院，陜西西安 710119)

摘要：利用弱困難性假設(shè)構(gòu)造強安全的加密系統(tǒng)在基于身份的加密(Identity-Based Encryption,IBE)中具有重要的理論與實際意義.本文基于弱困難性的判定性雙線性Diffie-Hellman假設(shè)，構(gòu)造了一個對于選擇明文攻擊安全的匿名的身份加密方案，解決了利用弱困難性假設(shè)構(gòu)造強安全的基于身份加密系統(tǒng)的問題，同時也解決了基于身份的加密系統(tǒng)的隱私保護問題.與現(xiàn)有的基于較強困難性假設(shè)的方案相比，新方案實現(xiàn)的條件更容易滿足，可以公開驗證而且效率更高.

關(guān)鍵詞:基于身份的加密；匿名；可公開驗證；選擇密文安全；判定性雙線性Diffie-Hellman假設(shè)

1引言

基于身份的加密體制是由Shamir[1]于1984年提出.與傳統(tǒng)公鑰加密體制不同，IBE中用戶的身份被轉(zhuǎn)化成公鑰，不需要公鑰設(shè)施(Public Key Infrastructure,PKI)分發(fā)公鑰證書，這樣可以提高加密效率.但發(fā)送者用接收者的身份信息作為公鑰加密消息，接收者的身份信息容易被敵手獲得，因而泄漏接收者的隱私.要保護接收者的身份信息，需要研究匿名的IBE方案.一個匿名IBE方案必須滿足以下條件：敵手從密文中無法得到接收者身份的任何信息，也無法通過公鑰和密文元組對身份進行驗證.

2001年，Boneh和Franklin[2]利用橢圓曲線上的雙線性對[3]構(gòu)造了一個實用的匿名IBE方案，在隨機預(yù)言機模型下，通過將雙線性Diffie-Hellman問題(BDH問題)歸約到 IBE方案的破解，證明了方案對于選擇密文攻擊(Chosen Ciphertext Attack,CCA)是安全的，但他們沒有提及方案的匿名性.

Canetti等人[4]指出在隨機預(yù)言機模型下證明安全的方案實際上未必安全.因為在方案實際執(zhí)行時，需要尋找具體的哈希函數(shù)或偽隨機函數(shù)來替換方案中的隨機預(yù)言機.而標準模型下的IBE方案通常只需要抗碰撞的單向函數(shù)，其安全性更可靠.因此Boneh和Franklin[2]提出了一個公開問題：能否在標準模型下構(gòu)造可證明安全的IBE方案.

Abdalla等[5]證明Waters[6]和Boneh-Boyen[7]的IBE方案不能達到匿名性，更進一步提出能否在標準模型下構(gòu)造匿名IBE.隨后出現(xiàn)了第一個不使用隨機預(yù)言機的匿名IBE方案[8].方案把身份信息隨機分成兩部分來保證不被識別，基于判定性雙線性Diffie-Hellman假設(shè)(Decisional Bilinear Diffie-Hellman Problem,DBDH)抵抗選擇身份攻擊-選擇明文攻擊(sID-CPA).

2006年，Gentry提出了兩個匿名IBE方案[9]，分別達到選擇明文安全和選擇密文安全.方案的公共參數(shù)很短，加密過程不需要進行雙線性對計算，并且基于判定的雙線性Diffie-Hellman指數(shù)的擴展(Decisional Augmented Bilinear Diffie-Hellman Exponent,Decisional ABDHE) 問題實現(xiàn)了緊性歸約.但是很難說明q-ABDHE下的緊性歸約比DBDH下的松散歸約強.

后來不少匿名IBE方案被提出，但很少有方案能基于弱困難問題達到強安全性.例如Wang等[10]提出了一個匿名的IBE方案，方案的安全性基于一些靜態(tài)的復(fù)雜假設(shè)，密文的匿名性利用合數(shù)階雙線性群的子群性質(zhì)來保證.方案的缺點是公共參數(shù)和密文長度較長，安全性和效率不高.

本文受文獻[9]啟發(fā)，基于DBDH問題構(gòu)造了一個在標準模型下安全的、可公開驗證的匿名IBE方案，解決了Boneh和Franklin提出的公開問題，也解決了Gentry所提出的問題.基于弱困難假設(shè)達到了強安全性，實現(xiàn)了CCA 安全性下DBDH問題到匿名IBE方案破解相對緊密的歸約，提高了加密效率，這使得方案既實用又安全，在實際應(yīng)用中更易實現(xiàn)且更有優(yōu)勢.

2預(yù)備知識

2.1雙線性映射

設(shè)G1和G2是階為大素數(shù)p的乘法群，映射e:G1×G1→G2是一個雙線性映射，e滿足以下性質(zhì)：

(1)雙線性：如果對于任意的P,Q∈G1和任意的a,b∈Z，都有e(aP,bQ)=e(P,Q)ab，我們就說e:G1×G1→G2是雙線性的.

(2)非退化性：這個映射不會將G1×G1中的所有對映射為G2的單位元.因為G1,G2同為素數(shù)階群，這意味著如果P是G1的單位元，那么e(P,P)是G2的單位元.

(3)可計算性：對于任意的P,Q∈G1，都有有效的算法來計算e(P,Q).

2.2困難性假設(shè)

W=e(P,P)abc∈G2

3基于身份的加密

3.1基于身份的加密的定義

一個基于身份的加密機制由初始化、私鑰生成、加密和解密四個隨機算法組成.

初始化輸入安全參數(shù)k，返回系統(tǒng)公開參數(shù)params和系統(tǒng)主密鑰master-key.系統(tǒng)公開參數(shù)包括：有限的消息空間M的描述，有限的密文空間C的描述.系統(tǒng)的公開參數(shù)params對外公布，秘密保存系統(tǒng)主密鑰master-key，僅由PKG所知.

私鑰生成輸入params、master-key和一個任意的c=Encrypt(params,ID,m)，返回對應(yīng)的私鑰d.這里ID為一個作為公鑰的任意長字符串，d為其對應(yīng)的私有的解密私鑰.Extract算法生成公鑰的對應(yīng)私鑰.

加密輸入params,ID和明文消息m∈M,輸出密文c∈C.

解密輸入params,密文c∈C和私鑰d，返回明文消息m∈M.

這些算法必須滿足一致性約束的標準，也就是說當d是由Extract算法生成的公鑰ID對應(yīng)的私鑰時，有下述計算成立：對于任意的m∈M，Decrypt(params,c,d)=m，這里

c=Encrypt(params,ID,m)

3.2安全模型

本節(jié)介紹了選擇密文攻擊下匿名IBE方案的安全模型.安全性證明通過下述游戲進行，其中有兩個參與者：A為敵手，B為挑戰(zhàn)者.

初始化B執(zhí)行Setup算法并把系統(tǒng)參數(shù)params發(fā)送給A.

階段1A適應(yīng)性的進行下列詢問：

加密詢問〈ID〉B對身份ID執(zhí)行Extract算法，并把對應(yīng)的私鑰返還給敵手.

解密詢問〈ID,C〉B首先對身份ID執(zhí)行Extract算法，然后用生成私鑰解密密文C，并把明文M或出錯信息返還給A.

挑戰(zhàn)A提交身份ID0,ID1和消息M0,M1給B，其中ID0,ID1都沒有在階段1中執(zhí)行過提取詢問，B隨即選擇j,k∈{0,1}，計算

C*=Encrypt(params,IDj,Mk)

并把C*返還給A.

階段2A繼續(xù)適應(yīng)性地詢問，但是不能對ID0,ID1進行提取詢問,或者對〈ID0,C*〉和〈ID1,C*〉進行解密詢問.

猜測A輸出j′,k′∈{0,1}，如果j′=j，k′=k則A贏得游戲.我們稱A為匿名的選擇性密文安全(ANON-IND-ID-CCA2)敵手，其優(yōu)勢定義為

定義1一個具有(t,q,ε)-ANON-IND-ID-CCA2安全性的IBE系統(tǒng)為在t時間內(nèi)所有ANON-IND-ID-CCA2挑戰(zhàn)者至多產(chǎn)生q次詢問，至多有ε的概率取得挑戰(zhàn)成功.

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

定義2一個具有(t,q,ε)-ANON-IND-ID-CPA安全性的IBE系統(tǒng)為在t時間內(nèi)所有ANON-IND-ID-CPA挑戰(zhàn)者至多產(chǎn)生q次詢問，至多有ε的概率取得挑戰(zhàn)成功.

4具體方案

4.1方案介紹

初始化公共參數(shù)為{g,g1,g2,H}，主密鑰為α.

其中β=H(C1,C2,C3,C4).由于e(g1,g2)和e(g,g1)都可以提前運算，所以加密階段不需要作對運算.

解密接收者首先計算β=H(C1,C2,C3,C4)，然后驗證下式是否成立：

C5=e(gβ,C3)e(C4,g1)β

(1)

若式(1)成立，則接收者可以使用私鑰d=(d1,d2,d3)解密.解密如下:

(2)

4.2正確性

如果C=(C1,C2,C3,C4,C5)是使用身份ID對m加密的有效密文，則可以對式(1)、(2)作如下驗證：

對于式(1)有:

=e(g,g1)βse(g,g1)βt

=e(g,g1)β(s+t)

=C5

對于式(2)有:

4.3安全性

假設(shè)DBDH是困難的，我們證明上一節(jié)的IBE方案是ANON-IND-ID-CCA安全的.

定理1如果選取的哈希函數(shù)H是一個普通的單向哈希函數(shù)，群G1上的DBDH問題是困難的，則我們的IBE方案是ANON-IND-ID-CCA安全的.

證明為了證明定理1，我們假設(shè)A能夠以ε的優(yōu)勢攻破上述IBE方案.我們可以構(gòu)建一個模擬器B和一個統(tǒng)計測試，通過調(diào)用敵手A的能力來解決G1中的DBDH問題.

方案證明過程中所使用的兩個分布R,D的定義如下：

分布R是一個隨機的五元組{g,gα,gb,gc,Z}∈G5，其中Z是隨機選取的;

分布D是五元組{g,gα,gb,gc,Z}∈G5，其中Z=e(g,g)αbc.

在統(tǒng)計測試中，從分布R或D中選取五元組{g,gα,gb,gc,Z}，進行如下構(gòu)造：建立一個模擬器B，用B來模擬對上述加密方案進行攻擊時敵手A的視圖(view)(所謂視圖是方案參與方的公共輸入，自己的秘密輸入、自己選擇的隨機數(shù)，以及整個過程中收到的所有消息序列)分布(隱藏比特k不屬于敵手的視圖).

如果分布的輸入來自D，模擬器可以完美的模擬真實加密方案，此時敵手擁有不可忽略的優(yōu)勢ε猜對隱藏比特k；當分布的輸入來自R，敵手的視圖與隱藏比特k是相互獨立的，即敵手猜對的優(yōu)勢是可忽略的.在運行模擬器和敵手的過程中，模擬器輸出一個比特k，敵手輸出一個比特k′，如果k=k′則輸出1，否則輸出0，這意味著統(tǒng)計測試可以區(qū)分來自R和D的分布.這里的證明思想借鑒了Cramer,Shoup[11]的證明方法.

下面給出模擬器B的工作模式和挑戰(zhàn)游戲過程：

初始化B生成系統(tǒng)參數(shù)，令g1=gα,g2=gb，并將系統(tǒng)參數(shù)g,g1,g2發(fā)給敵手A.

d=(d1,d2,d3)

所以，模擬的私鑰d=(d1,d2,d3)是對應(yīng)身份ID的一個有效私鑰.

A繼續(xù)發(fā)起解密詢問(ID,C)，B在回答解密詢問之前先生成ID對應(yīng)的私鑰.然后，按照之前的解密算法進行解密，并將解密結(jié)果發(fā)給A.

首先計算：

然后計算：

β=H(C1,C2,C3,C4),C5=e(g,g1)β(c+ρ)

如果模擬器B的輸入來自分布D，即Z=e(g,g)αbc，則密文形式為：

C=(C1,C2,C3,C4,C5)

顯然，C是明文Mk的一個有效加密密文.

如果模擬器B的輸入來自分布R，即Z是G2中的一個隨機元素.這種情況下，加密預(yù)言機的輸出密文不合法，敵手從密文得不到B所選擇的比特k的任何信息.

階段2A繼續(xù)發(fā)起私鑰提取詢問和解密詢問，B的回復(fù)同階段1.

猜測最終，敵手A輸出兩個猜測j′,k′∈{0,1}.如果j=j′,k=k′，B輸出1，否則輸出0.

以上完成了模擬描述，下面引入兩個引理來證明定理1.

引理1當模擬器B的輸入{g,gα,gb,gc,Z}來自D分布，敵手A的視圖和隱藏比特{j,k}的聯(lián)合分布與真實環(huán)境統(tǒng)計不可區(qū)分.

證明根據(jù)以上模擬過程，當模擬不提前結(jié)束時，敵手A的視圖和隱藏比特{j,k}的聯(lián)合分布只在挑戰(zhàn)密文階段有效，所以只需證明在該階段敵手A的視圖和隱藏比特{j,k}的聯(lián)合分布與真實環(huán)境統(tǒng)計不可區(qū)分.

已知輸入來自分布D，則Z=(g,g)abc，敵手A對身份ID發(fā)起私鑰提取詢問和解密詢問時，B的模擬都是完全正確的.B的回答不會給A提供任何附加信息.

在多次IND-ID-CCA攻擊的模擬構(gòu)成的統(tǒng)計測試中，每次模擬器的輸入都是隨機的，且模擬挑戰(zhàn)密文時所用的隨機數(shù)也是隨機選取的，所以每次模擬所生成的挑戰(zhàn)密文是相互獨立的.敵手A的視圖和隱藏比特{j,k}的聯(lián)合分布與真實環(huán)境統(tǒng)計不可區(qū)分.

引理2當模擬者B的輸入來自R分布，敵手的視圖和隱藏比特{j,k}的分布是相互獨立的.

注意到，當輸入來自R分布時，挑戰(zhàn)階段的密文是無效密文，所以解密階段對有效密文的回答對敵手沒有幫助，而對無效密文的回答可能會對敵手有幫助，所以通過以下兩個斷言證明預(yù)言機可以判定密文的有效性.

斷言1若在攻擊過程中，解密預(yù)言機拒絕所有無效密文，則隱藏比特{j,k}的分布與敵手的視圖是相互獨立的.

已知輸入來自分布R，則Z=e(g,g)z.在挑戰(zhàn)階段，挑戰(zhàn)密文如下：

由于z是從G1中隨機選取的，所以z和敵手A的視圖無關(guān)，更進一步的說，e(g,g)zMk是一次完美填充.所以隱藏比特{j,k}的分布與敵手的視圖是相互獨立的.

斷言2解密預(yù)言機拒絕所有無效密文，接受無效密文的概率是可忽略的.

對于敵手A提交的密文C=(C1,C2,C3,C4,C5)，解密預(yù)言機可以通過以下兩個等式判斷所給密文的有效性：

(3)

5方案對比

本節(jié)綜合分析計算復(fù)雜度、通信復(fù)雜度以及安全性方面的性能.表1將現(xiàn)有的匿名IBE方案與我們提出的新方案進行了全面的對比.通過比較可以發(fā)現(xiàn)，新方案的主要優(yōu)勢在于降低了困難假設(shè)強度，同時提高了安全性，而效率方面幾乎沒有犧牲.綜合來看，新方案具有很大的優(yōu)勢.

表1　方案對比

6結(jié)束語

匿名IBE在提高加密效率和保護用戶隱私等方面都具有很大的優(yōu)勢.本文針對Gentry提出的公開問題，構(gòu)建了一個標準模型下CCA安全的匿名IBE方案.新方案有以下優(yōu)勢：基于的DBDH問題困難性較弱，加密復(fù)雜度更低，可以公開驗證等，彌補了DBDH問題下CCA安全的匿名IBE的空缺.

目前，匿名IBE方案并不是很多.研究在標準模型下基于更自然的困難假設(shè)、具有緊性歸約的、高效的、抗CCA安全的匿名IBE方案仍然是一個值得深入研究的問題.

參考文獻

[1]Shamir A.Identity-based cryptosystems and signature schemes[A].Advances in Cryptology 1984[C].Berlin:Springer-Verlag,1984.47-53.

[2]Boneh D,Franklin M.Identity-based encryption from the Weil pairing[A].Advances in Cryptology-CRYPTO 2001[C].Berlin:Springer-Verlag,2001.213-229.

[3]Menezes A J,Okamoto T,Vanstone S A.Reducing elliptic curve logarithms to logarithms in a finite field[J].IEEE Transactions on Information Theory,1993,39(5):1639-1646.

[4]Canetti R,Goldreich O,Halevi S.The random oracle methodology,revisited[J].Journal of the ACM (JACM),2004,51(4):557-594.

[5]Abdalla M,Bellare M,Catalano D,et al.Searchable encryption revisited:Consistency properties,relation to anonymous IBE,and extensions[J].Journal of Cryptology,2008,21(3):350-391.

[6]Waters B.Efficient identity-based encryption without random oracles[A].Advances in Cryptology-EUROCRYPT 2005[C].Berlin:Springer-Verlag,2005.114-127.

[7]Boneh D,Boyen X.Secure identity based encryption without random oracles[J].Lecture Notes in Computer Science,2004.443-459.

[8]Boyen X,Waters B.Anonymous hierarchical identity-based encryption (without random oracles)[A].Advances in Cryptology-CRYPTO 2006[C].Berlin:Springer-Verlag,2006.290-307.

[9]C Gentry.Practical identity-based encryption without random oracles[A].Advances in Cryptology-EUROCRYPT 2006[C].Berlin:Springer-Verlag,2006.445-464.

[10]王皓,徐秋亮.抗適應(yīng)性選擇身份攻擊的匿名HIBE方案[J].計算機學報,2011,34(1):25-37.

WANG Hao,XU Qiu-liang.Anonymous HIBE scheme secure against full adaptive-ID attacks[J].Chinese Journal of Computers,2011,34(1):25-37.(in Chinese)

[11]Cramer R,Shoup V.A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[A].Advances in Cryptology-CRYPTO 1998 [C].Berlin:Springer-Verlag,1998.13-25.

李順東男，1963年12月生于河南平頂山.1984、1987年在西安工程大學獲工學學士、碩士學位；2003年在西安交通大學獲計算機科學與技術(shù)工學博士學位.現(xiàn)為陜西師范大學計算機科學學院教授、博士生導(dǎo)師.主要從事密碼學與信息安全研究.

E-mail:shundong@snnu.edu.cn

楊坤偉男，1990年5月出生于陜西咸陽.陜西師范大學計算機科學學院碩士研究生.主要研究方向為密碼學與信息安全.

E-mail: yangkunwei@163.com

A Publicly Verifiable Anonymous IBE Scheme in the Standard Model

LI Shun-dong，YANG Kun-wei，GONG Lin-ming，MAO Qing，LIU Xin

(SchoolofComputerScience,ShaanxiNormalUniversity，Xi′an,Shaanxi710119,China)

Abstract:Constructing a stronger security encryption system based on a weaker computationally hard assumption is of great theoretical and practical importance in identity-based encryption.To solve this problem,we,based on a weaker assumption that the decisional bilinear Diffie-Hellman problem is hard,construct an anonymous identity-based encryption scheme which is secure against adaptively chosen ciphertext attack.This scheme can prevent an identity-based encryption system from disclosing privacy.Compared with the existing schemes based on stronger computationally hard assumption,the prerequisite of our scheme can be satisfied more easily,besides,it is publicly verifiable and more efficient.

Key words:identity-based encryption;anonymous;publicly verifiable;chosen ciphertext attack;decisional bilinear Diffie-Hellman assumption

作者簡介

DOI:電子學報URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.027

中圖分類號:TP309

文獻標識碼：A

文章編號：0372-2112 (2016)03-0673-06

基金項目:國家自然科學基金(No.61070189,No.61272435,No.61373020)

收稿日期:2014-10-28;修回日期:2015-4-23；責任編輯：覃懷銀