BGN-型類同態(tài)IBE方案的構(gòu)造與分析

戴曉明　張　薇　鄭志恒

(武警工程大學(xué)信息安全保密重點(diǎn)實(shí)驗(yàn)室　陜西 西安 710086)

?

BGN-型類同態(tài)IBE方案的構(gòu)造與分析

戴曉明張薇鄭志恒

(武警工程大學(xué)信息安全保密重點(diǎn)實(shí)驗(yàn)室陜西 西安 710086)

基于身份的公鑰密碼體制(IBE)與傳統(tǒng)的公鑰密碼體制不同，在IBE中用戶公鑰是與用戶身份相關(guān)的可識(shí)別的一串字符，這就為加密后的數(shù)據(jù)提供了更靈活的訪問控制。BGN是2005年提出的一種類同態(tài)加密方案，該方案能對(duì)密文進(jìn)行任意次加法和一次乘法運(yùn)算，但是并不是一種IBE方案。為得到類同態(tài)的IBE方案，以滿足網(wǎng)絡(luò)中對(duì)身份類加密體制的需求，在BGN方案的基礎(chǔ)上，基于二次剩余假設(shè)和子群判定問題構(gòu)造了一種新的具有類同態(tài)性質(zhì)的IBSHE加密方案，在隨機(jī)預(yù)言機(jī)模型下證明了該方案的CPA安全性。

同態(tài)加密基于身份的加密雙線性映射二次剩余問題子群判定問題

0　引　言

加密體制的同態(tài)性已成為新型密碼體制的一個(gè)重要設(shè)計(jì)目標(biāo)。具有同態(tài)性質(zhì)的加密方案允許在服務(wù)器端直接對(duì)密文進(jìn)行運(yùn)算，用戶只需對(duì)返回的密文結(jié)果解密即可，所以同態(tài)密碼在保證數(shù)據(jù)安全性的同時(shí)，能顯著降低數(shù)據(jù)服務(wù)的通信量及運(yùn)算量。因而將同態(tài)加密與具體應(yīng)用相結(jié)合，借鑒成熟的數(shù)學(xué)工具，構(gòu)造滿足實(shí)際應(yīng)用需要的高效的新型同態(tài)加密方案，深入研究同態(tài)加密體制在具體場(chǎng)合的應(yīng)用，并構(gòu)造相關(guān)的應(yīng)用協(xié)議，具有十分重要的理論和實(shí)踐意義。

1995年，Benaloh[1]提出了一種支持有限次加法操作的密碼體制，這是第一個(gè)以同態(tài)性為設(shè)計(jì)目標(biāo)的公鑰密碼，隨后產(chǎn)生的各種同態(tài)加密方案都只支持加法操作。直到2005年，Boneh等[2]提出了BGN方案，該方案可對(duì)密文做一次乘法和任意多次加法運(yùn)算，是自同態(tài)加密被提出以來的首個(gè)類同態(tài)加密方案，方案被證明在密文不可區(qū)分的選擇明文攻擊下(Ciphertext indistinguishability under chosen plaintext attacks:IND-CPA)安全。2010年，Gentry等在格上實(shí)現(xiàn)了BGN方案[3]。2009年，Gentry[4]開創(chuàng)性地利用自舉和壓縮的構(gòu)造方法，提出了一個(gè)基于理想格的全同態(tài)加密方案。2010年，Dijk等[5]利用Gentry的構(gòu)造方法構(gòu)造了整數(shù)上的全同態(tài)加密方案DGHV，該方案使用了成熟的困難問題，所以成為第一個(gè)被廣泛認(rèn)為安全的全同態(tài)方案。此后相繼誕生了幾個(gè)全同態(tài)加密方案[6-9]，但這些全同態(tài)加密方案實(shí)現(xiàn)起來都非常復(fù)雜，效率很低，并不實(shí)用。2013年，Gentry等人[10]基于LWE問題，利用近似特征值方法提出了一個(gè)新的全同態(tài)加密方案，一定程度上簡(jiǎn)化了全同態(tài)加密的實(shí)現(xiàn)，但與實(shí)際應(yīng)用還存在不小的差距。

1984年,Shamir[11]提出了基于身份的公鑰密碼體制，用戶公鑰是與用戶身份相關(guān)的可識(shí)別的一串字符，這就為加密后的數(shù)據(jù)提供了更靈活的訪問控制。2001年，Cocks[12]基于二次剩余假設(shè)提出了第一個(gè)較為實(shí)用的IBE方案。隨后基于身份加密方案的應(yīng)用和研究廣泛開展，研究人員利用橢圓曲線上的雙線性對(duì)和多線性對(duì)設(shè)計(jì)出了其他的IBE方案[13-15]。2014年，Ducas等人[16]利用NTRU格上的特殊分布提出了第一個(gè)基于格的IBE方案，并將密鑰和密文大小控制在2～4 kbs，使得該方案較為實(shí)用。

2013年,Clear等人[17]基于Cocks的IBE方案構(gòu)造了一個(gè)具有加法同態(tài)性質(zhì)的IBE方案(XOR-Homomorphic IBE)。由于該方案只實(shí)現(xiàn)了加法同態(tài)性質(zhì)，所以并不能同時(shí)滿足乘法同態(tài)的運(yùn)算要求,很大程度上限制了IBE方案的功能。2014年,Clear等人[18]又提出了一個(gè)自舉的全同態(tài)IBFHE方案，并能擴(kuò)展應(yīng)用到屬性基加密(ABFHE方案)，但由于全同態(tài)的引入，不可避免的造成了計(jì)算復(fù)雜度太高。

為了實(shí)現(xiàn)IBE方案同態(tài)性質(zhì)上的改進(jìn)，同時(shí)考慮到全同態(tài)加密實(shí)現(xiàn)上的復(fù)雜性，本文選擇了效率更高的類同態(tài)加密方案。將文獻(xiàn)[12]中的IBE方案與文獻(xiàn)[2]中的類同態(tài)加密方案結(jié)合，構(gòu)造了一個(gè)新的具有類同態(tài)性質(zhì)的IBSHE方案，分別論證了該方案能滿足對(duì)密文進(jìn)行任意多次加法運(yùn)算和一次乘法運(yùn)算，并在隨機(jī)預(yù)言機(jī)模型下證明了該方案的安全性。

1　相關(guān)基礎(chǔ)理論

1.1同態(tài)加密

同態(tài)加密方案含有四個(gè)算法：密鑰生成算法(Keygen)、加密算法(Encrypt)、解密算法(Decrypt)和密文計(jì)算算法(Evaluate)。其中前三個(gè)算法提供加密和解密功能，密文計(jì)算算法是同態(tài)加密方案的核心所在，因?yàn)橥瑧B(tài)的目的就是要實(shí)現(xiàn)對(duì)密文的直接計(jì)算。將同態(tài)性質(zhì)描述如下：

1) 生成系統(tǒng)參數(shù)和公私鑰，Gen(1λ)→(pk,sk),?c∈C,?m1,…,mt∈M。

2) 運(yùn)用同態(tài)加密對(duì)明文進(jìn)行加密運(yùn)算，得到相應(yīng)密文：

?c1,…,ct←Enc(pk,m1),…,Enc(pk,mt)

3) 密文計(jì)算算法對(duì)電路C(電路C代表一個(gè)函數(shù)或者一個(gè)功能)上輸入的一組密文c=(c1,…,ci)(其中ci←encrypt(mi))進(jìn)行計(jì)算。

4) 解密算法對(duì)計(jì)算后的密文解密，得到與對(duì)明文作相應(yīng)運(yùn)算的結(jié)果相同的解密結(jié)果：

C(m1,…,mt)=Dec(sk,Eval(pk,C,c1,…,ct))

1.2雙線性映射

G、G1是由大素?cái)?shù)p生成的循環(huán)群，p為生成元，階都為素?cái)?shù)p，若群G、G1中的離散對(duì)數(shù)問題均為困難問題，則所定義的雙線性映射e:G×G→G1滿足的性質(zhì)為：

2) 非退化性存在g1,g2∈G，使得e(g1,g2)≠1。

3) 可計(jì)算性存在有效的算法使得對(duì)任意g1,g2∈G，可以計(jì)算出e(g1,g2)。

滿足以上條件的雙線性映射e可以利用有限域上的超奇異橢圓曲線中的Weil對(duì)或Tate對(duì)構(gòu)造出來。

1.3子群判定問題

定義算法Φ，給定安全參數(shù)τ∈Z+,運(yùn)行Φ(τ)生成五元組(〗q1,q2,G,G1,e)，其中群G,G1具有相同的階n=q1q2，e:G×G→G1是雙線性映射。輸入τ，算法Φ運(yùn)行如下：

1) 生成兩個(gè)隨機(jī)的τ-bits素?cái)?shù)q1,q2，并計(jì)算n=q1q2；

2) 生成如1.2節(jié)所述具有雙線性映射的群G,G1，g是群G的一個(gè)元素，且有雙線性映射e:G×G→G1；

3) 輸出(q1,q2,G,G1,e)。

子群判定問題是指：給定(n,G,G1,e)和一個(gè)元素x∈G，如果x的階是q1則輸出‘1’，否則輸出‘0’。上述問題也可以描述為：在群的階n的因子分解未知的情況下，判定一個(gè)元素x是否屬于G的一個(gè)子群。

對(duì)于攻擊算法S，解決子群判定問題的優(yōu)勢(shì)SD-AdvS(τ)可以定義如下：

定義1如果一個(gè)多項(xiàng)式時(shí)間算法S的優(yōu)勢(shì)SD-AdvS(τ)可忽略，則Φ滿足子群判定假設(shè)。

1.4二次剩余問題

設(shè)p是一個(gè)奇素?cái)?shù)，p不整除a，如果同余方程x2≡a(modp)有解，則稱a為模p的二次剩余，否則稱a為模p的二次非剩余。將二次剩余的集合記作QR(p)。

2　方案具體實(shí)現(xiàn)

2.1加解密算法

基于文獻(xiàn)[12]中提出的IBE方案與文獻(xiàn)[2]中提出的類同態(tài)加密方案的思想，本文提出了一個(gè)具有類同態(tài)性質(zhì)的IBSHE方案。該方案包括四個(gè)算法：Setup,KeyGen,Encrypt,Decrypt。

Setup(1λ)→PK,MSK：算法輸入安全參數(shù)λ，根據(jù)參數(shù)λ輸出系統(tǒng)的公鑰參數(shù)PK和系統(tǒng)的主密鑰MSK。隨機(jī)選擇大素?cái)?shù)p,q，使p,q滿足條件p≡q≡3(mod4)，計(jì)算合數(shù)N=pq，運(yùn)行1.3節(jié)給定的算法￡(λ)生成元組(p,q,G,G1,e)，其中群G、G1具有相同的階N=pq，群G,G1滿足雙線性映射e:G×G→G1。在G中隨機(jī)選擇元素g、u，令h=uq。得到系統(tǒng)的公鑰參數(shù)為：PK=(N,G,G1,e,g,h)。系統(tǒng)的主私鑰為：MSK=(p,q)。

所以，最終得到的用戶私鑰為：SKid=(id,r,p)。

得到的密文為：ψ=(s1,s2)。

2.2同態(tài)性質(zhì)分析

定義2一個(gè)同態(tài)加密方案：密鑰生成算法(Keygen)、加密算法(Encrypt)、解密算法(Decrypt)和密文計(jì)算算法(Evaluate)。對(duì)于給定的電路C，任意由Keygen生成的密鑰對(duì)(pk,sk)，任意t個(gè)明文m1,m2,…,mt以及經(jīng)同態(tài)加密后每個(gè)明文對(duì)應(yīng)的密文c1,c2,…,ct(其中ci←encrypt(mi))，如果方案滿足：

Decrypt(sk,Evaluate(pk,C,c))=C(m1,m2,…,mt)

則稱該同態(tài)加密方案是正確的。

本節(jié)主要是證明2.1節(jié)中提出的IBSHE方案具有類同態(tài)性質(zhì)。

證明方案具有加法同態(tài)性質(zhì)：系統(tǒng)的公鑰為(n,G,G1,e,g,h)，當(dāng)r2≡a(modN)時(shí)，系統(tǒng)對(duì)明文m1,m2∈{0,1}分別進(jìn)行加密，返還給用戶的密文為C1,C2∈G(其中C1=gbhe1,C2=gche2)，用戶通過計(jì)算C=C1C2he3=g(b+c)h(e1+e2+e3)=g(b+c)he，進(jìn)一步計(jì)算可得到：

從而論證了方案具有加法同態(tài)性質(zhì)。

證明方案具有乘法同態(tài)性質(zhì)：利用雙線性映射的性質(zhì)，我們可以實(shí)現(xiàn)對(duì)密文的一次乘法同態(tài)運(yùn)算。令g1=e(g,g),h1=e(g,h)，g1,h1的階分別為n,p，定義h=gαq(α∈Z)。對(duì)于兩個(gè)明文加密得到密文為：C1=gbhe1∈G,C2=gche2∈G，需要對(duì)密文做如下運(yùn)算使得運(yùn)算結(jié)果解密后與直接對(duì)明文做乘法運(yùn)算所得結(jié)果相等：

1) 隨機(jī)選擇e3∈Z2

2) 計(jì)算C=e(C1,C2)hr∈G1，計(jì)算過程如下：

3) 進(jìn)一步計(jì)算得到：

則可以計(jì)算：

應(yīng)該注意到的是，由于雙線性對(duì)本身性質(zhì)的限制，所以只允許對(duì)密文進(jìn)行一次乘法操作，但仍可以對(duì)一次乘法操作后的密文繼續(xù)進(jìn)行加法操作。從而論證了方案具有一次乘法同態(tài)性質(zhì)。

綜合以上所述，2.1節(jié)中提出的IBSHE方案可以對(duì)密文進(jìn)行一次乘法操作和任意多次加法操作，方案具有類同態(tài)性質(zhì)。

3　安全性分析

3.1安全模型

IBE方案的安全模型定義如下：

1) Init：攻擊者聲明即將挑戰(zhàn)的身份id*；

2) Setup：挑戰(zhàn)者運(yùn)行Setup算法并將得到的系統(tǒng)公鑰參數(shù)發(fā)送給攻擊者；

3) Key Query：攻擊者請(qǐng)求用戶id的私鑰，限制是id≠id*，挑戰(zhàn)者調(diào)用密鑰生成算法并將所得私鑰SK發(fā)送給攻擊者；

4) Challenge：攻擊者提交兩條等長的密文m0和m1，攻擊者隨機(jī)選擇一個(gè)明文并對(duì)其加密，將加密的密文發(fā)送給攻擊者(攻擊者可再重復(fù)進(jìn)行Key Query的過程，直至攻擊者認(rèn)為有把握進(jìn)行猜測(cè)為止)；

5) Guess：攻擊者猜測(cè)挑戰(zhàn)者加密的是哪一條明文，猜對(duì)則攻擊者獲勝。

在上述攻擊游戲中，當(dāng)且僅當(dāng)攻擊者獲勝的概率可忽略時(shí)，才認(rèn)為IBE方案是安全的。

3.2安全性證明

上述方案的安全性可用以下定理來描述

定義3一個(gè)IND-ID-CPA敵手A利用多項(xiàng)式時(shí)間算法在子群判定問題困難性假設(shè)下以ε的優(yōu)勢(shì)贏得3.1節(jié)中的游戲，當(dāng)且僅當(dāng)優(yōu)勢(shì)ε可忽略時(shí)，2.1節(jié)中構(gòu)造的IBSHE方案具有IND-ID-CPA安全性。

證明我們?cè)陔S機(jī)預(yù)言機(jī)模型下證明方案的安全性：

假設(shè)敵手A試圖攻破本方案，A構(gòu)造一個(gè)多項(xiàng)式時(shí)間攻擊算法S用于具體實(shí)施攻擊。S運(yùn)行如下：

1) A選擇身份id*為攻擊目標(biāo)，S將id*轉(zhuǎn)發(fā)給C；

2) S從挑戰(zhàn)者C那里得到公鑰PK，將它傳送給A；

3) S以H′(id)·h-2作為對(duì)id的哈希值(顯然應(yīng)有限定條件id≠id*，其中H′是S的隨機(jī)預(yù)言機(jī))，這個(gè)結(jié)果在ZN[+1]中均勻分布；

4) S根據(jù)id生成密鑰K(id)·h-1，其中K是S的密鑰生成模型；

5) 令a=H(id*)。敵手輸出m0,m1，挑戰(zhàn)者隨機(jī)選擇b∈{0,1}，將mb加密，首先計(jì)算出(c,d)，再計(jì)算c(x)=gchr∈G,d(x)=gdhr∈G(其中(c,d)是對(duì)明文b加密得到的初始密文，(c(x),d(x))是對(duì)(c,d)進(jìn)一步進(jìn)行同態(tài)加密得到的密文)，將(c(x),d(x))發(fā)送給攻擊者A；

6) A根據(jù)所得到的信息輸出b′，如果b′=b,則敵手攻擊成功。

4　結(jié)　語

本文通過Cocks的IBE方案與Boneh的BGN方案相結(jié)合，構(gòu)造了一個(gè)新的具有類同態(tài)性質(zhì)的IBSHE方案。對(duì)方案的同態(tài)性質(zhì)進(jìn)行了論證并基于隨機(jī)預(yù)言機(jī)模型證明了方案的安全性。接下來將繼續(xù)對(duì)同態(tài)加密以及基于身份和基于屬性的加密體制進(jìn)行研究，進(jìn)一步的工作希望可以更為深入地研究同態(tài)加密在基于身份和基于屬性的加密體制中的具體應(yīng)用，并構(gòu)造相關(guān)的應(yīng)用協(xié)議。

[1] Benaloh J.Dense probabilistic encryption[C].SAC 1994.1995:121-145.

[2] Boneh D,Goh E J,Nissim K.Evaluating 2-DNF formulas on ciphertexts[C]//LNCS.2005:325-341.

[3] Gentry C,Halevi S,Vaikuntanathan V.A simple BGN-type cryptosystem from LWE[C]//LNCS.2010:506-522.

[4] Gentry C.Fully homomorphic encryption using ideal lattices[C]//Proc.of STOC.2009:169-178.

[5] Dijk M,Gentry C,Halevi S,et al.Fully Homomorphic encryption over the integers[C]//Proc of EUROCRYPT’10,2010:24-43.

[6] Brakerski Z,Vaikuntanathan V.Fully homomorphic encryption from ring-LWE and security key dependent messages[C]//Proc. of CRYPTO’11. 2011:501.

[7] Brakerski Z,Vailuntanathany V.Efficient fully homomorphic encryption from(standard) LWE[C]//ECCC.2011:109-138.

[8] Brakerski Z,Gentry C,Vaikuntanathan V.(Leveled) fully homomorphic encryption without bootstrapping[C]//Proc of the 3rd Innovations in Theoretical Computer Science Conference,2012:309-325.

[9] Gentry C,Halevi S,Smart N P.Fully homomorphic encryption with polylog overhead[C]//Proc.of EUROCRYPT’12.2012:465-482.

[10] Gentry C,Sahai A,Waters B.Homomorphic encryption from learning with errors:conceptually-simpler,asymptotically-faster,attribute-based[C]//Proc. of CRYPTO’2013.2013:75-92.

[11] Shamir A.Identity-based cryptosystems and signature schemes[C]//Pro. of CRYPTO’84 on Advances in Cryptology,1984:47-53.

[12] Cocks C.An identity-based encryption based on quadratic residues[C]//Proc of International Conference on Cryptography and Coding,2001:360-363.

[13] Ye Zhang,Mamous N.Anonymous fuzzy identity-based encryption for similarity search[C]//Cryptology ePrint Archive,2009:496.

[14] Sharmila S,Selvi D,ScreeVivek S,et al.Identity-based online/offline encryption and signcryption schemes revisited[C]//LNCS.2011:111-127.

[15] Park S,Lee K,Lee D H.New constructions of revocable identity-based encryption from multilinear maps[OL].2013.http://eprint.iacr.org/2015/.

[16] Ducas L,Lyubashevsky V,Prest T.Efficient identity-based encryption over NTRU lattices[OL].2014.http://eprint.iacr.org/2015/.

[17] Clear M,Hughes A,Tewari H.Homomorphic encryption with access policies:characterization and new constructions[C]//Africacrypt,2013:39.

[18] Clear M,McGoldrick C.Bootstrappableidentity-basedfully homomorphic encryption[OL].2014.http://eprint.iacr.org/2015/.

CONSTRUCTION AND ANALYSIS OF THE HOMOMORPHIC IBE SCHEME OF BGN TYPE

Dai XiaomingZhang WeiZheng Zhiheng

(Key Laboratory of Information Security, Engineering University of Armed Police Force,Xi’an 710086,Shaanxi,China)

Since the identity-based public key encryption(IBE) is different from traditional public key encryption, the public key in IBE is a string of characters which is related to the identity of the user, thus it provides the encrypteddata with a more flexible access control.BGN is a homomorphic encryption scheme proposed in 2005, which is able to do arbitrary additions and one multiplication to the encrypted message, but it is not an IBE scheme still.On the basis of the BGN scheme, a new homomorphic IBSHE scheme based on quadratic residue and subgroup decisional problemis constructedto obtain a homomorphic IBE scheme which satisfies the demand of identity-based encryptionscheme in network. Also, the CPA security of the scheme is proved by random oracle model.

Homomorphic encryptionIdentity-based encryptionBilinear mapQuadratic residue problemSubgroup decisional problem

2015-10-28。國家自然科學(xué)基金項(xiàng)目(61272492，6110 3230)。戴曉明，碩士生，主研領(lǐng)域：公鑰密碼學(xué)。張薇，副教授。鄭志恒，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2016.09.072