BGN-型類同態IBE方案的構造與分析

戴曉明　張　薇　鄭志恒

(武警工程大學信息安全保密重點實驗室　陜西 西安 710086)

?

BGN-型類同態IBE方案的構造與分析

戴曉明張薇鄭志恒

(武警工程大學信息安全保密重點實驗室陜西 西安 710086)

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

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

0　引　言

加密體制的同態性已成為新型密碼體制的一個重要設計目標。具有同態性質的加密方案允許在服務器端直接對密文進行運算，用戶只需對返回的密文結果解密即可，所以同態密碼在保證數據安全性的同時，能顯著降低數據服務的通信量及運算量。因而將同態加密與具體應用相結合，借鑒成熟的數學工具，構造滿足實際應用需要的高效的新型同態加密方案，深入研究同態加密體制在具體場合的應用，并構造相關的應用協議，具有十分重要的理論和實踐意義。

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

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

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

為了實現IBE方案同態性質上的改進，同時考慮到全同態加密實現上的復雜性，本文選擇了效率更高的類同態加密方案。將文獻[12]中的IBE方案與文獻[2]中的類同態加密方案結合，構造了一個新的具有類同態性質的IBSHE方案，分別論證了該方案能滿足對密文進行任意多次加法運算和一次乘法運算，并在隨機預言機模型下證明了該方案的安全性。

1　相關基礎理論

1.1同態加密

同態加密方案含有四個算法：密鑰生成算法(Keygen)、加密算法(Encrypt)、解密算法(Decrypt)和密文計算算法(Evaluate)。其中前三個算法提供加密和解密功能，密文計算算法是同態加密方案的核心所在，因為同態的目的就是要實現對密文的直接計算。將同態性質描述如下：

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

2) 運用同態加密對明文進行加密運算，得到相應密文：

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

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

4) 解密算法對計算后的密文解密，得到與對明文作相應運算的結果相同的解密結果：

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

1.2雙線性映射

G、G1是由大素數p生成的循環群，p為生成元，階都為素數p，若群G、G1中的離散對數問題均為困難問題，則所定義的雙線性映射e:G×G→G1滿足的性質為：

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

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

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

1.3子群判定問題

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

1) 生成兩個隨機的τ-bits素數q1,q2，并計算n=q1q2；

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

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

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

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

定義1如果一個多項式時間算法S的優勢SD-AdvS(τ)可忽略，則Φ滿足子群判定假設。

1.4二次剩余問題

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

2　方案具體實現

2.1加解密算法

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

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

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

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

2.2同態性質分析

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

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

則稱該同態加密方案是正確的。

本節主要是證明2.1節中提出的IBSHE方案具有類同態性質。

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

從而論證了方案具有加法同態性質。

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

1) 隨機選擇e3∈Z2

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

3) 進一步計算得到：

則可以計算：

應該注意到的是，由于雙線性對本身性質的限制，所以只允許對密文進行一次乘法操作，但仍可以對一次乘法操作后的密文繼續進行加法操作。從而論證了方案具有一次乘法同態性質。

綜合以上所述，2.1節中提出的IBSHE方案可以對密文進行一次乘法操作和任意多次加法操作，方案具有類同態性質。

3　安全性分析

3.1安全模型

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

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

2) Setup：挑戰者運行Setup算法并將得到的系統公鑰參數發送給攻擊者；

3) Key Query：攻擊者請求用戶id的私鑰，限制是id≠id*，挑戰者調用密鑰生成算法并將所得私鑰SK發送給攻擊者；

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

5) Guess：攻擊者猜測挑戰者加密的是哪一條明文，猜對則攻擊者獲勝。

在上述攻擊游戲中，當且僅當攻擊者獲勝的概率可忽略時，才認為IBE方案是安全的。

3.2安全性證明

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

定義3一個IND-ID-CPA敵手A利用多項式時間算法在子群判定問題困難性假設下以ε的優勢贏得3.1節中的游戲，當且僅當優勢ε可忽略時，2.1節中構造的IBSHE方案具有IND-ID-CPA安全性。

證明我們在隨機預言機模型下證明方案的安全性：

假設敵手A試圖攻破本方案，A構造一個多項式時間攻擊算法S用于具體實施攻擊。S運行如下：

1) A選擇身份id*為攻擊目標，S將id*轉發給C；

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

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

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

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

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

4　結　語

本文通過Cocks的IBE方案與Boneh的BGN方案相結合，構造了一個新的具有類同態性質的IBSHE方案。對方案的同態性質進行了論證并基于隨機預言機模型證明了方案的安全性。接下來將繼續對同態加密以及基于身份和基于屬性的加密體制進行研究，進一步的工作希望可以更為深入地研究同態加密在基于身份和基于屬性的加密體制中的具體應用，并構造相關的應用協議。

[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。國家自然科學基金項目(61272492，6110 3230)。戴曉明，碩士生，主研領域：公鑰密碼學。張薇，副教授。鄭志恒，碩士生。

TP3

A

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