非對稱雙線性對下的基于身份的加密方案*

徐 磊,許春根,竇本年

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

非對稱雙線性對下的基于身份的加密方案*

徐 磊,許春根,竇本年

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

基于身份的加密是一種直接以用戶的身份作為公鑰的加密方案。自提出以來,利用雙線性對實現基于身份的加密方案的案例已經有很多,但是這些方案大都是采用對稱的雙線性對,即要求作為映射輸入的兩個群相同。這無疑縮小了映射中所選取的橢圓曲線的范圍,將在一種更一般的條件下,即在非對稱雙線性對下,基于判定性雙線性Diffe-Hellman(BDHE)難解問題在標準模型下構造出一種新型的基于身份的加密方案,并證明其在標準模型下具有不可區分的選擇身份的選擇明文(IND-sID-CPA)安全性。

基于身份的加密方案 非對稱雙線性對 標準模型 公鑰加密

0 引 言

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

1 基礎知識

1.1 雙線性對及其上的困難問題

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

設G,,Gt是3個階為大素數p的乘法循環群。g∈G,∈分別是G,的生成元。e:G×→Gt是從(G,)到Gt的一個映射。稱e:G×→Gt是一個雙線性映射,如果:

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

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

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

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

現在我們給出非對稱情況下的基于雙線性的Decision-BDH問題DBDH的困難性假設。

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

(DBDH)假設:若對于任意多項式時間t敵手A,和構造的算法B,其針對群(G,,Gt)上的DBDH問題的優勢均小于ε,則稱(G,,Gt)上的(t,ε)-DBDH假設成立。

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

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

Setup:挑戰者輸入安全參數k,返回系統參數params和系統主密鑰msk。其中系統參數params作為系統參數公開,主密鑰msk由PKG秘密保存。

KeyGeneration:將params,msk,以及用戶的身份ID={0,1}*作為輸入,返回一個私鑰d。這里ID是一個任意長度的字符串,將被作為系統參數用來加密,d由用戶自己保存,作為解密密鑰。

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

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

(攻擊游戲)我們在選擇身份攻擊下使用敵手與挑戰者游戲定義IBE的安全性,游戲規則如下:

Init:敵手A先給定一個他想挑戰的身份ID*=。

Setup:挑戰者運行Setup算法,將得到的系統參數params發送給敵手,私鑰msk自己保存。

Phase1:敵手詢問q1,q2,…qm,其中qi是下面描述:

-Extraction query＜IDi＞:挑戰者通過運行Extract算法對敵手的詢問返回對應于身份IDi的私鑰di。然后把它發送給敵手。

Challenge:一旦敵手確定Phase1結束,立刻輸出他想挑戰的兩個長度相等的明文M0,M1∈M。挑戰者隨機選取β∈{0,1},并且令挑戰密文

再將密文C*發送給敵手。

Phase2:敵手提出更多的詢問qm+1,qm+2,…,qn,這里qi為下面情形:

-Extraction query＜IDi＞:這里IDi≠ID*,挑戰者如Phase1做出回應。

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

2 基于身份的加密算法的構造

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

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

Encryption:設M∈Gt,則對于身份為ID的用戶加密過程為:隨機選取t∈Zp,然后利用公共參數構造密文如下:

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

由此可知,該方案是可執行的。

3 安全性分析

我們在標準模型下,利用(G,,Gt)上的DBDH假設證明構造的IBE方案的安全性。先給出如下定理:

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

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

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

Initialization:此游戲從敵手A先選擇一個他想攻擊的身份ID*=開始。

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

然后,對于身份ID={I1,I2,…,In},我們設U?{1,2,…,n}是滿足Ii=1的所有i的集合。為了分析簡便,我們定義下面3個函數:

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

否則,B隨機選取r∈Zp,然后構造密鑰:

當且僅當L(ID)≠0(modp)時,算法B才進行如上計算,為了分析方便,我們設該游戲繼續進行下去的充分條件為R(ID)≠0。

Challenge:當Phase1結束,敵手B立刻輸出他想挑戰的兩個長度相等的明文M0,M1∈M。如果,則算法B隨機選取一個猜測β。否則,隨機選取γ∈{0,1},構造密文

此時,C*是在敵手選擇的公鑰ID*=下對密文Mγ的一個有效加密。

另一方面,如果我們說Z是Gt中的任意一個元素。那么所得到的的密文將不會給出任何與γ相關的信息。

Phase2:敵手重復Phase1,提出更多的詢問。算法B做出同前相應的返回輸出。

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

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

當B的7元組輸入來自PBDH時,從A的角度上,這個算法B就等同于一次真實攻擊,且A必須滿足。

當B的7元組輸入來自RBDH時,則敵手A的優勢是可忽略的,即,因此a,b,c是均勻取自Zp中的,Z在Gt中也是隨機選取的,這時候我們有:則定理4.1得證。

4 結 語

文中介紹了利用非對稱的雙線性對在標準模型下構建一個IBE加密方案,并基于Decision-BDH難解問題,給出了其具有選擇身份的選擇明文安全性的證明。該方案不僅使得構建加密方案使用的橢圓曲線更加廣泛,使得攻破的難度增加許多。而且具有很好的拓展性,比如可以將其演變成標準模型下基于身份的分層加密方案,還有隨機預言模型下的一些加密方案等。后面我們還將著手分別在對稱和非對稱的雙線性對模式下構造出更多的具有更多性質的加密方案[16-17],并給出與其相對應的簽名,匿名簽名[18],環簽名[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] 周楝淞,楊潔,譚平嶂,等.基于身份的密碼系統及其實現[J].通信技術,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].計算機工程與與應用,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] 劉振華,胡予濮,牟寧波,等.新的標準模型下基于身份的環簽名方案[J].電子與信息學報,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] 徐國愚,陳性元,杜學繪.大規模延遲容忍網絡中基于分級身份簽名的認證方案研究[J].電子與信息學報,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-),男,博士,教授,主要研究方向為信息安全與編碼、密碼技術應用研究;

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

竇本年(1976-),男,博士,講師,主要研究方向為計算機應用技術、多用戶環境下數字簽名的構造。

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-),男,碩士,主要研究方向為信息安全、現代密碼學及其算法分析;

2014-05-09;

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

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

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