徐 磊,許春根,竇本年

(南京理工大學(xué)理學(xué)院,江蘇南京210094)

非對(duì)稱(chēng)雙線性對(duì)下的基于身份的加密方案*

徐 磊,許春根,竇本年

(南京理工大學(xué)理學(xué)院,江蘇南京210094)

基于身份的加密是一種直接以用戶(hù)的身份作為公鑰的加密方案。自提出以來(lái),利用雙線性對(duì)實(shí)現(xiàn)基于身份的加密方案的案例已經(jīng)有很多,但是這些方案大都是采用對(duì)稱(chēng)的雙線性對(duì),即要求作為映射輸入的兩個(gè)群相同。這無(wú)疑縮小了映射中所選取的橢圓曲線的范圍,將在一種更一般的條件下,即在非對(duì)稱(chēng)雙線性對(duì)下,基于判定性雙線性Diffe-Hellman(BDHE)難解問(wèn)題在標(biāo)準(zhǔn)模型下構(gòu)造出一種新型的基于身份的加密方案,并證明其在標(biāo)準(zhǔn)模型下具有不可區(qū)分的選擇身份的選擇明文(IND-sID-CPA)安全性。

基于身份的加密方案 非對(duì)稱(chēng)雙線性對(duì) 標(biāo)準(zhǔn)模型 公鑰加密

0 引 言

基于身份的加密體制[1]提供了一種直接以接受者的家庭住址,電話號(hào)碼等信息作為公鑰的加密方法。這種體制自提出以來(lái)就受到了廣泛的關(guān)注,因?yàn)榕c傳統(tǒng)的公鑰加密體制相比,基于身份的加密體制的公鑰不需要認(rèn)證中心認(rèn)證,這大大減少了證書(shū)分發(fā)與管理的復(fù)雜性。在2002年,Dan Boneh[2]用雙線性對(duì)構(gòu)造出了第一個(gè)完整方案以后,大批學(xué)者利用雙線性對(duì)中的困難問(wèn)題相繼構(gòu)造出了一系列基于身份的加密[3-7],基于身份的分層加密[8-10]及簽名[11-14]方案。但這些方案大部分都是在對(duì)稱(chēng)的雙線性對(duì)下進(jìn)行的,即要求G=,這種限制使得可以用來(lái)構(gòu)造基于身份的加密方案的橢圓曲線種類(lèi)受到了很大的限制,安全性也降低了很多。為了解決這個(gè)問(wèn)題,Dan Boneh在2010年又提出了在非對(duì)稱(chēng)的雙線性映射條件下,構(gòu)造出標(biāo)準(zhǔn)模型下的一種新型的有效的基于身份的加密方案[15]。這種方案降低了雙線性函數(shù)對(duì)橢圓曲線選擇的限制,且有更好的安全性。本文將圍繞這一思想給出一個(gè)安全的有效的加密方案。

1 基礎(chǔ)知識(shí)

1.1 雙線性對(duì)及其上的困難問(wèn)題

為了構(gòu)造我們所需的方案,這里先介紹雙線性映射及雙線性群。我們使用[4,15]中的定義:

設(shè)G,,Gt是3個(gè)階為大素?cái)?shù)p的乘法循環(huán)群。g∈G,∈分別是G,的生成元。e:G×→Gt是從(G,)到Gt的一個(gè)映射。稱(chēng)e:G×→Gt是一個(gè)雙線性映射,如果:

1)映射e:G×→Gt可以被有效計(jì)算。

2)雙線性:對(duì)所有的u∈G,v∈,a,b∈ZP,有e(ua,vb)=e(u,v)ab。

3)非退化性:e(g,)≠1。

上述是雙線性對(duì)的基本定義,一般情況下,我們對(duì)G和沒(méi)有太多的限制,即認(rèn)定G=,且大部分的密碼學(xué)方案也是在此前提下構(gòu)造的,但是這限制了構(gòu)造方案的廣泛性,因此這里我們將在一個(gè)更加廣泛的條件下構(gòu)造出我們的加密方案,即不要求G=。這就使得我們可以利用的橢圓曲線的范圍更加廣泛,且方案會(huì)有更好的安全性。

現(xiàn)在我們給出非對(duì)稱(chēng)情況下的基于雙線性的Decision-BDH問(wèn)題DBDH的困難性假設(shè)。

(Decision-BDH)問(wèn)題:給定(g,,ga,gc,a,b,Z)∈G3×3×Gt,其中g(shù)∈G,∈,Z∈Gt。對(duì)于未知的a,b,c∈ZP。判定e(g,)abc=Z是否成立。通常,對(duì)于多項(xiàng)式時(shí)間敵手A,和構(gòu)造的算法B,將其針對(duì)群(G,,Gt)上的DBDH問(wèn)題的優(yōu)勢(shì)定義為:

(DBDH)假設(shè):若對(duì)于任意多項(xiàng)式時(shí)間t敵手A,和構(gòu)造的算法B,其針對(duì)群(G,,Gt)上的DBDH問(wèn)題的優(yōu)勢(shì)均小于ε,則稱(chēng)(G,,Gt)上的(t,ε)-DBDH假設(shè)成立。

1.2 基于身份的加密體制及其安全性描述

(基于身份的加密體制)一個(gè)基于身份的加密方案有下面4個(gè)隨機(jī)算法組成:

Setup:挑戰(zhàn)者輸入安全參數(shù)k,返回系統(tǒng)參數(shù)params和系統(tǒng)主密鑰msk。其中系統(tǒng)參數(shù)params作為系統(tǒng)參數(shù)公開(kāi),主密鑰msk由PKG秘密保存。

KeyGeneration:將params,msk,以及用戶(hù)的身份ID={0,1}*作為輸入,返回一個(gè)私鑰d。這里ID是一個(gè)任意長(zhǎng)度的字符串,將被作為系統(tǒng)參數(shù)用來(lái)加密,d由用戶(hù)自己保存,作為解密密鑰。

Encryption:將params,ID,M∈M作為輸入,返回密文C∈C。

Decryption:輸入params,密文C,私鑰d,輸出明文M。

(攻擊游戲)我們?cè)谶x擇身份攻擊下使用敵手與挑戰(zhàn)者游戲定義IBE的安全性,游戲規(guī)則如下:

Init:敵手A先給定一個(gè)他想挑戰(zhàn)的身份ID*=。

Setup:挑戰(zhàn)者運(yùn)行Setup算法,將得到的系統(tǒng)參數(shù)params發(fā)送給敵手,私鑰msk自己保存。

Phase1:敵手詢(xún)問(wèn)q1,q2,…qm,其中qi是下面描述:

-Extraction query＜IDi＞:挑戰(zhàn)者通過(guò)運(yùn)行Extract算法對(duì)敵手的詢(xún)問(wèn)返回對(duì)應(yīng)于身份IDi的私鑰di。然后把它發(fā)送給敵手。

Challenge:一旦敵手確定Phase1結(jié)束,立刻輸出他想挑戰(zhàn)的兩個(gè)長(zhǎng)度相等的明文M0,M1∈M。挑戰(zhàn)者隨機(jī)選取β∈{0,1},并且令挑戰(zhàn)密文

再將密文C*發(fā)送給敵手。

Phase2:敵手提出更多的詢(xún)問(wèn)qm+1,qm+2,…,qn,這里qi為下面情形:

-Extraction query＜IDi＞:這里IDi≠I(mǎi)D*,挑戰(zhàn)者如Phase1做出回應(yīng)。

Guess:最后,敵手輸出猜測(cè)β′∈{0,1}。如果β′=β,敵手獲勝。

2 基于身份的加密算法的構(gòu)造

Setup:系統(tǒng)參數(shù)由下述方法生成,對(duì)生成元對(duì)為(g,)的雙線性對(duì)(G,),隨機(jī)選取α∈Zp,設(shè)g1=gα,1=α,隨機(jī)選取∈及長(zhǎng)度為n的向量W=(i),i∈。再隨機(jī)選取β∈Zp,令0=αβ,并計(jì)算v=e(g,0)=e(g,)αβ。最后,公開(kāi)系統(tǒng)參數(shù)params={G,,Gt,g,,g1,1,v,W},保留系統(tǒng)主密鑰0。

KeyGeneration:設(shè)ID={I1,I2,…,In}是一個(gè)n比特的字符串代表身份,U?{1,2,…,n}是滿足Ii=1的所有i的集合。則基于身份ID的密鑰按如下路徑生成:首先隨機(jī)選取r∈Zp,用戶(hù)ID私鑰構(gòu)造如下:

Encryption:設(shè)M∈Gt,則對(duì)于身份為ID的用戶(hù)加密過(guò)程為:隨機(jī)選取t∈Zp,然后利用公共參數(shù)構(gòu)造密文如下:

Decryption:設(shè)C=(C1,C2,C3)是消息M在身份為ID的用戶(hù)下加密的密文。則C可以用dID解密,過(guò)程如下:

由此可知,該方案是可執(zhí)行的。

3 安全性分析

我們?cè)跇?biāo)準(zhǔn)模型下,利用(G,,Gt)上的DBDH假設(shè)證明構(gòu)造的IBE方案的安全性。先給出如下定理:

定理4.1:假設(shè)(G,,Gt)上的DBDH假設(shè)成立。則前面所定義的IBE方案對(duì)任意的qID次詢(xún)問(wèn)是具有(t′,qID,ε)-選擇身份選擇明文安全性(IND-sID-CPA)。

具體的說(shuō),如果針對(duì)上述方案,A是一個(gè)具有ε優(yōu)勢(shì)的(qID-IND-sID-CPA)敵手。那么存在一個(gè)(G,,Gt)上的DBDH敵手B使得其在游戲中與A有大致相同的優(yōu)勢(shì)ε。

證明:假設(shè)敵手A攻擊IBE方案的優(yōu)勢(shì)為ε。我們構(gòu)造一個(gè)算法B,它能夠解決(G,)上的DBDH問(wèn)題。算法B被給定一個(gè)隨機(jī)的7元組(g,,ga,gc,a,b,Z)作為輸入,7元組從PBDH(Z=e(g,)abc)或RBDH(Z在Gt中是獨(dú)立同分布的)中選取。算法B的目標(biāo)是:如果Z=e(g,)abc,輸出β=1。否則,輸出β=0。為了進(jìn)行如下游戲,令g1=ga,1=a,g2=gc,2=b,則與敵手A互動(dòng)的選擇身份的游戲如下:

Initialization:此游戲從敵手A先選擇一個(gè)他想攻擊的身份ID*=開(kāi)始。

Setup:為了生成系統(tǒng)參數(shù),算法B設(shè)m=4qID,再隨機(jī)選取k∈{0,1,…,n},以及長(zhǎng)度為n的向量h=(hi)和h′,z′,其中h′以及向量h中的元素均取自于0到m-1,記H*=(h′,h)。再選取z=(zi),z′,向量z中的元素及z′均在Zp內(nèi)取值。這些值都僅限算法B自己知道。

然后,對(duì)于身份ID={I1,I2,…,In},我們?cè)O(shè)U?{1,2,…,n}是滿足Ii=1的所有i的集合。為了分析簡(jiǎn)便,我們定義下面3個(gè)函數(shù):

Phase1:敵手A詢(xún)問(wèn)私鑰。假設(shè)敵手詢(xún)問(wèn)身份ID的私鑰。如果R(ID)=0,則B中止游戲并隨機(jī)輸出β的猜測(cè)值β′。

否則,B隨機(jī)選取r∈Zp,然后構(gòu)造密鑰:

當(dāng)且僅當(dāng)L(ID)≠0(modp)時(shí),算法B才進(jìn)行如上計(jì)算,為了分析方便,我們?cè)O(shè)該游戲繼續(xù)進(jìn)行下去的充分條件為R(ID)≠0。

Challenge:當(dāng)Phase1結(jié)束,敵手B立刻輸出他想挑戰(zhàn)的兩個(gè)長(zhǎng)度相等的明文M0,M1∈M。如果,則算法B隨機(jī)選取一個(gè)猜測(cè)β。否則,隨機(jī)選取γ∈{0,1},構(gòu)造密文

此時(shí),C*是在敵手選擇的公鑰ID*=下對(duì)密文Mγ的一個(gè)有效加密。

另一方面,如果我們說(shuō)Z是Gt中的任意一個(gè)元素。那么所得到的的密文將不會(huì)給出任何與γ相關(guān)的信息。

Phase2:敵手重復(fù)Phase1,提出更多的詢(xún)問(wèn)。算法B做出同前相應(yīng)的返回輸出。

Guess:最后,敵手A輸出猜測(cè)γ′∈{0,1}。算法B輸出如下游戲結(jié)果:

如果γ′=γ,敵手獲勝。輸出1,即意味著Z=e(g,)abc成立。否則輸出0,諭示著Z≠e(g,)abc。

當(dāng)B的7元組輸入來(lái)自PBDH時(shí),從A的角度上,這個(gè)算法B就等同于一次真實(shí)攻擊,且A必須滿足。

當(dāng)B的7元組輸入來(lái)自RBDH時(shí),則敵手A的優(yōu)勢(shì)是可忽略的,即,因此a,b,c是均勻取自Zp中的,Z在Gt中也是隨機(jī)選取的,這時(shí)候我們有:則定理4.1得證。

4 結(jié) 語(yǔ)

文中介紹了利用非對(duì)稱(chēng)的雙線性對(duì)在標(biāo)準(zhǔn)模型下構(gòu)建一個(gè)IBE加密方案,并基于Decision-BDH難解問(wèn)題,給出了其具有選擇身份的選擇明文安全性的證明。該方案不僅使得構(gòu)建加密方案使用的橢圓曲線更加廣泛,使得攻破的難度增加許多。而且具有很好的拓展性,比如可以將其演變成標(biāo)準(zhǔn)模型下基于身份的分層加密方案,還有隨機(jī)預(yù)言模型下的一些加密方案等。后面我們還將著手分別在對(duì)稱(chēng)和非對(duì)稱(chēng)的雙線性對(duì)模式下構(gòu)造出更多的具有更多性質(zhì)的加密方案[16-17],并給出與其相對(duì)應(yīng)的簽名,匿名簽名[18],環(huán)簽名[19]以及簽密方案。

[1] SHAMIR Adi.Identity-Based Cryptosystems and Signature Schemes[C]//Advances in Cryptology-CRYPTO’84,LNCS(196).Berlin Heidelberg:Springer-Verlag, 1985:213-229.

[2] BONEH Dan,FRANKLIN Matt.Identity-Based Encryption from the Weil Pairing[C]//Advances in Cryptology Crypto 2001,LNCS(2139).Berlin Heidelberg:Springer-Verlag,2001:213-229.

[3] BONEH Dan,BOYEN Xavier.Efficient Selective Identity-Based Encryption without Random Oracles[C]//Advances in Cryptology-EUROCRYPT 2004,LNCS(3027).Berlin Heidelberg:Springer-Verlag,2004:223-238.

[4] WATERS Brent.Efficient Selective Identity-Based Encryption without Random Oracles[C]//Advances in Cryptology-EUROCRYPT 2005,LNCS(3494).Berlin Heidelberg:Springer-Verlag,2005:114-127.

[5] 周楝淞,楊潔,譚平嶂,等.基于身份的密碼系統(tǒng)及其實(shí)現(xiàn)[J].通信技術(shù),2010,43(06):68-70.

ZHOU Lian-song,YANG Jie,TAN Ping-zhang,et al.Implementation of Identity-based Cryptosystem[J].Communications Technology:2010,43(6):68-70.

[6] SAHAI Amit,WATERS Brent.Fuzzy Identity-Based Encryption[C]//Advances in Cryptology-EUROCRYPT 2005,LNCS(3494).Berlin Heidelberg:Springer-Verlag,2005:457-473.

[7] GALINDO David.Chosen-Ciphertext Secure Identity-Based Encryption from Computational Bilinear Diffie-Hellman Pairing[C]//Pairing-Based Cryptography-Pairing 2010,LNCS(6487).Berlin Heidelberg:Springer -Verlag,2010:367-376.

[8] HORWITZ Jeremy,LYNN Ben.Toward Hierarchical I-dentity Based Encryption[J].EUROCRYPT:2002, LNCS(2332):466-481.

[9] GENTRY Graig,HALEVI Shai.Hierarchical Identity Based Encryption with Polynomially Many Levels[C]// TCC 2009,LNCS(5444).Berlin Heidelberg:Springer-Verlag.2009:437-456.

[10] 張席,楊玲.一種高效的基于身份的分層加密方案[J].計(jì)算機(jī)工程與與應(yīng)用,2012,48(24):101-105.

ZHANG Xi,YANG Ling.Efficient Hierarchical IDBased Encryption Scheme[J].Computer Engineering and Applications:2012,48(24):101-105.

[11] 劉振華,胡予濮,牟寧波,等.新的標(biāo)準(zhǔn)模型下基于身份的環(huán)簽名方案[J].電子與信息學(xué)報(bào),2009, 31(07):1727-1731.

LIU Zhen-hua,HU Yu-pu,MU Ling-bo,MA Hua. New Identity-Based Ring Signature in the Standard Model[J].Jounal of Electronics&Information Technology:2009,31(7):1727-1731.

[12] 徐國(guó)愚,陳性元,杜學(xué)繪.大規(guī)模延遲容忍網(wǎng)絡(luò)中基于分級(jí)身份簽名的認(rèn)證方案研究[J].電子與信息學(xué)報(bào),2013,35(11):2615-2622.

XU Guo-yu,CHEN Xing-yuan,DU Xue-hui.An Authentication Scheme Using Hierarchical Identity Based Signature in Large-scale Delay Tolerant Networks[J]. Jounal of Electronics&Information Technology:2013,35 (11):2615-2622.

[13] BONEH Dan,BOYEN Xavier.Short Signatures without Random Oracles[C]//Advances in Cryptology-EUROCRYPT 2004,LNCS(3027).BerlinHeidelberg: Springer-Verlag,2004:56-73.

[14] ZHOU Cai-xue,WAN Zhou,XI Wei-dong.Provable Certificateless Generalized Signcryption Scheme Designs [C]//Codes and Cryptography,71(2).Berlin Heidelberg:Springer-Verlag,2014:331-346.

[15] BONEH Dan.Efficient Selective Identity-Based Encryption without Random Oracles[C]//Journal of Cryptology 2011,LNCS(24).Berlin Heidelberg:Springer-Verlag,2011:659-693.

[16] SU Le,LIM Hoon-wei,LING San,WANG Huaxiong.Revocable IBE Systems with Almost Constant-Size Key Update[C]//Pairing-Based Cryptography Pairing 2013,LNCS(8365).BerlinHeidelberg: Springer-Verlag,2014:168-185.

[17] HOHENBERGER Susan,WATERS Brent.Online/Offline Attribute-Based Encryption[C]//Public-Key Cryptography-PKC 2014,LNCS(8383).Berlin Heidelberg:Springer-Verlag,2014:293-310.

[18] CHEN Jie,LIM Hoon-wei,SAN Ling,WANG Huaxiong,HOETECK Wee.Shorter IBE and Signatures via AsymmetricPairings[C]//Pairing2012,LNCS (7708).Berlin Heidelberg:Springer-Verlag,2013: 122-140.

[19] LIBERT Benoit,JOYE Marc.Group Signatures with Message-Dependent Opening in the Standard Model [C]//Cryptology CT-RSA 2014,LNCS(8366).Berlin Heidelberg:Springer-Verlag,2014:286-306.

XU Lei(1990-),male,M.Sci.,majoring in information security,modern cryptography and algorithmic analysis.

許春根(1969-),男,博士,教授,主要研究方向?yàn)樾畔踩c編碼、密碼技術(shù)應(yīng)用研究;

XU Chun-gen(1969-),male,Ph.D.,professor,principally working at information security and codes,modern cryptography technology research.

竇本年(1976-),男,博士,講師,主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)、多用戶(hù)環(huán)境下數(shù)字簽名的構(gòu)造。

DOU Ben-nian(1976-),male,Ph.D.,lecturer,mainly working at computer application technology,multi-users environment digital signature schemes.

Identity-Based Encryptionfrom the Asymmetric Bilinear Pairings

XU Lei,XU Chun-gen
(School of science,Nanjing university of science and technology,Nanjing Jiangsu 210094,China)

Identity-based encryption is a method which directly uses the user’s identity as its public key. Since it appears,there are a lot of identity-based encryption schemes from bilinear pairings,but most of these schemes uses symmetric bilinear pairings as their math tools,namely the groups as it put in the bilinear mapping should be the same one.This would greatly reduce the scope of the available elliptic curves in the encryption schemes.This paper proposes a new type of identity-based encryption scheme from the asymmetric bilinear pairings without using random oracles,in a more general bilinear pairings conditions, and proves that it has indistinguishable selective-ID CPA security by reducing it to decision-BDH problem under the standard model.

identity-based encryption;asymmetric bilinear pairings;standard model;public-key encryption

TP309

A

1002-0802(2014)08-0941-05

10.3969/j.issn.1002-0802.2014.08.020

徐 磊(1990-),男,碩士,主要研究方向?yàn)樾畔踩F(xiàn)代密碼學(xué)及其算法分析;

2014-05-09;

2014-06-09 Received date：2014-05-09;Revised date：2014-06-09

江蘇省自然科學(xué)基金(No.BK20131353)

Foundation Item:Natural Science Foundation of Jiangsu Province(No.BK20131353)