戴曉明 張薇 鄭志恒 李鎮(zhèn)林

摘要：針對傳統(tǒng)的基于身份的加密（IBE）方案不能夠?qū)γ芪闹苯舆M行計算這一功能上的缺陷，提出了一個新的IBE方案。該方案利用Gentry等提出的同態(tài)轉(zhuǎn)化機制，結(jié)合Agrawal等構(gòu)造的層次型IBE方案，構(gòu)造了一個具有全同態(tài)性質(zhì)的層次型IBE方案。與Gentry等提出的全同態(tài)加密（GSW）方案（GENTRY C， SAHAI A， WATERS B. Homomorphic encryption from learning with errors： conceptuallysimpler， asymptoticallyfaster， attributebased. CRYPTO 2013： Proceedings of the 33rd Annual Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2013： 75-92）和Clear等提出的全同態(tài)IBE（CM）方案（CLEAR M， MCGOLDRICK C. Bootstrappable identitybased fully homomorphic encryption. CANS 2014： Proceedings of 13th International Conference on Cryptology and Network Security. Berlin： Springer， 2014： 1-19）相比，該方案構(gòu)造方法更加自然，空間復雜度由立方級降低到平方級，效率更高。在當前云計算背景下，有助于基于容錯學習（LWE）的全同態(tài)加密方案從理論向?qū)嵺`轉(zhuǎn)化。通過性能分析并在隨機預(yù)言機模型下驗證了所提方案具有完全安全下的選擇明文攻擊（INDIDCPA）安全性。

關(guān)鍵詞：

全同態(tài)加密；基于身份的加密；近似特征向量；容錯學習問題；密文校平

中圖分類號： TP309.7 文獻標志碼：A

0引言

全同態(tài)加密能夠在不解密的條件下實現(xiàn)對密文的任意計算，解密后可以達到相應(yīng)明文計算的效果。全同態(tài)加密的這一優(yōu)良特性使得它具有廣闊的應(yīng)用前景，如代理計算、電子投票、云存儲中的密文搜索、安全多方計算等?！叭瑧B(tài)加密”的概念是由Rivest等[1]于1978年首次提出。此后，學者們對構(gòu)造同態(tài)加密方案進行了不斷的探索，也提出了一些方案[2-4]，但這些方案在同態(tài)計算能力上非常有限，只能稱為半同態(tài)或者類同態(tài)加密方案。2009年，Gentry[5]開創(chuàng)性地利用自舉和壓縮的構(gòu)造方法，基于理想格提出了第一個全同態(tài)加密方案。這一突破性工作掀起了全同態(tài)加密的研究熱潮，出現(xiàn)了許多按照Gentry所給框架進行設(shè)計的全同態(tài)加密方案[6-8]。這種框架具有以下的缺點：為了取得自舉性，需要對類同態(tài)方案的解密電路進行“壓縮”，這需要一個額外的安全假設(shè)（稀疏子集和問題），導致方案的安全性較弱；在同態(tài)計算一個電路時，需要對每個電路門通過同態(tài)解密來進行密文更新，由于同態(tài)解密計算復雜度較高，導致方案效率很低。

2013年，Gentry等[9]不再基于Gentry的初始框架，而是基于近似特征向量構(gòu)造了一個全同態(tài)加密（GentrySahaiWaters， GSW）方案，不需要密鑰交換技術(shù)和模交換技術(shù)就可以實現(xiàn)層次型全同態(tài)加密，方案效率更高，且該方案的安全性基于容錯學習（Learning With Errors， LWE）問題，密文的計算就是矩陣的加法與乘法，因此是非常自然的一個全同態(tài)加密方案。

Shamir[10]提出了基于身份的公鑰加密（IdentityBased Encryption， IBE）體制，其中用戶公鑰是與用戶身份相關(guān)的可識別的一串字符，這就為數(shù)據(jù)提供了更靈活的訪問控制，但在當前云計算的背景下，用戶的隱私信息將會以密文形式上傳到云端；但傳統(tǒng)的IBE并不支持任何對密文的計算，所以傳統(tǒng)的IBE已經(jīng)不能滿足多用戶條件下對于隱私信息的保護和操作，構(gòu)造具有全同態(tài)性質(zhì)甚至類同態(tài)性質(zhì)的IBE方案成為一個公開問題。

在探索構(gòu)造具有同態(tài)性質(zhì)的IBE方案的過程中，主要產(chǎn)生了以下成果：2010年，Gentry等[11]利用文獻[4]中的類同態(tài)方案構(gòu)造了一個具有類同態(tài)性質(zhì)的IBE方案（IdentityBased Somewhat Homomorphic Encryption， IBSHE）。2013年，Clear等[12]基于Cocks[13]于2001年提出的IBE方案構(gòu)造了一個具有加法同態(tài)性質(zhì)的IBE方案，但該方案不能滿足乘法同態(tài)的運算要求，同態(tài)計算能力十分有限。因而構(gòu)造具有全同態(tài)性質(zhì)的IBE方案依然是一個開放的難題。同年，Gentry等[9]首次提出具有全同態(tài)性質(zhì)的層次型IBE方案，并提供了一種轉(zhuǎn)化機制，可以將滿足一定條件的IBE方案轉(zhuǎn)化為全同態(tài)IBE方案（IdentityBased Fully Homomorphic Encryption， IBFHE），該轉(zhuǎn)化機制同樣適用于滿足一定條件的基于屬性的加密（Attribute Based Encryption， ABE， ABE）方案的轉(zhuǎn)化。2014年，Clear等[14]又提出了一個自舉的IBFHE方案，同樣能擴展應(yīng)用到基于屬性的加密方案，但由于采用了自舉的構(gòu)造方法實現(xiàn)全同態(tài)，不可避免地造成計算復雜度太高。

針對以上問題，本文利用GSW方案提出的轉(zhuǎn)化機制，結(jié)合2010年Agrawal等[15]提出的層次型IBE（Hierarchical IdentityBased Encryption， HIBE）方案，構(gòu)造了一個新的層次型IBFHE（Hierarchical IdentityBased Fully Homomorphic Encryption， HIBFHE）方案，摒棄了以往基于LWE的同態(tài)加密方案利用重新線性化實現(xiàn)全同態(tài)的方式，而是使用了更為高效的近似特征向量的方式，對密文進行加、乘運算直接對應(yīng)到矩陣的加、乘運算，構(gòu)造方法上更加自然，空間復雜度也由立方級降低到平方級，這對于基于LWE的全同態(tài)加密方案從理論向?qū)嵺`轉(zhuǎn)化是非常關(guān)鍵的。此外，本文方案在同態(tài)運算的過程中，不像以往的同態(tài)加密算法需要解密密鑰的參與，因而支持只擁有公開參數(shù)的用戶對同一目標身份下的密文進行同態(tài)運算，這也正是GSW方案能夠與普通IBE方案相結(jié)合的根本原因。本文方案與原GSW方案相比，效率上有很大提高，文中進行了效率分析，并在隨機預(yù)言機模型下證明該基于身份的層次型全同態(tài)加密方案對于完全安全下的選擇明文攻擊（Indistinguishability of the IdentityBased Encryption Scheme under ChosenPlaintext Attack， INDIDCPA）安全。

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

1.1LWE問題和GvpSAP

Regev[16]對LWE問題有詳細描述，下面進行簡要介紹。

定義1給定安全參數(shù)λ，令整數(shù)維n=n（λ），整數(shù)q=q（λ）≥2， χ=χ（λ）是Z上的一個分布。LWEn，q， χ問題就是區(qū)分以下兩個分布：1）分布（ai，bi）隨機取自Zn+1q；2）隨機選擇s ← Znq，ai ← Znq，ei ← χ，令bi=〈ai，s〉+ei，然后生成（ai，bi）∈Zn+1q，LWEn，q， χ假設(shè)就是LWEn，q， χ問題是困難的。

為了簡化運算，將向量bi‖ai作為矩陣A的行，重新定義s ← （1，-s），這樣無論矩陣A是否是隨機矩陣或者s的第一個元素是否是1，都能保證生成的向量e=A·s的元素取自分布χ。

定義2對于格的維系數(shù)n和一個給定的數(shù)d，GapSVPγ問題是作出判定：n維格是擁有一個長度比d短的向量還是任何向量長度都比γ（n）·d大。

定理1[17]利用模n次多項式解決n維LWE問題意味著存在最壞情況的n維格上困難問題（如GapSVP）的高效解決方案。

1.2全同態(tài)加密本文的公式存在問題，即打開公式編輯器看到的公式，與word中看到的公式不一致，經(jīng)過校對，現(xiàn)在已調(diào)整為word所顯示的公式，請作者核對公式是否有誤？若有，請單獨指出來。

同態(tài)加密方案含有4個算法：密鑰生成算法（KeyGen）、加密算法（Encrypt）、解密算法（Decrypt）和密文計算算法（Evaluate）。其中前3個算法提供加密和解密功能，密文計算算法是同態(tài)加密方案的核心所在，因為同態(tài)的目的就是要實現(xiàn)對密文的直接計算。將同態(tài)性質(zhì)描述如下。

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

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

c1，c2，…，ct ← Enc（pk，m1），Enc（pk，m2），…，Enc（pk，mt）

3）密文計算算法對布爾電路Cir上輸入的一組密文c=（c1，c2，…，ci）（其中ci ← encrypt（mi））進行計算輸出一個新的密文c′。

4）解密算法對經(jīng)過同態(tài)計算后的密文解密，得到與對明文作相應(yīng)運算的結(jié)果相同的解密結(jié)果：

Cir（m1，m2，…，mt）=Dec（sk，Eval（pk，Cir，c1，c2，…，ct））

定義3同態(tài)加密的正確性。對于給定的電路Cir，任意由KeyGen生成的密鑰對（pk，sk），任意t個明文m1，m2，…，mt以及經(jīng)同態(tài)加密后每個明文對應(yīng)的密文c1，c2，…，ct（其中ci ← encrypt（mi）），如果方案滿足：

Dec（sk，Evaluate（pk，Cir，c））=C（m1，m2，…，mt）

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

定義4全同態(tài)加密。如果對于所有的算術(shù)電路類，方案都具有同態(tài)性質(zhì)，則稱方案為全同態(tài)加密方案。

1.3HIBE方案及安全模型

IBE方案包括4個算法：Setup、KeyGen、Encrypt、Decrypt。其中：Setup算法生成系統(tǒng)主密鑰（MSK，MPK），KeyGen（MSK，id）算法輸出身份id的私鑰skid，Enc（MPK，id， μ）算法輸出在身份id下對明文μ的加密密文c，Dec（skid，c）算法對密文c進行解密（前提是私鑰skid是在身份id下的）。通常KeyGen算法也被記作Extract算法，與Setup算法中出現(xiàn)的密鑰生成加以區(qū)分，以免造成混淆。

HIBE方案可以解決單私鑰生成器（Private Key Generator， PKG）負載過重的問題，并使其適合分布式環(huán)境下IBE方案的部署和應(yīng)用。在HIBE方案中，身份信息不再是字符串而是向量，HIBE方案有第5個算法叫作Derive算法，它可以利用身份信息id′=（id1，id2，…，idl）和該身份對應(yīng)的私鑰skid′，生成身份id=（id1，id2，…，idl，…，idk）對應(yīng)的私鑰skid，該私鑰與運行KeyGen算法對身份id輸出的私鑰相同。

在下面的描述中，設(shè)k為安全參數(shù)。以O(shè)Der表示模擬用戶密鑰產(chǎn)生算法的預(yù)言機。

定義5深度為d的HIBE方案在選擇明文攻擊下的安全性。如果任何概率多項式時間（Probabilistic Polynomial Time， PPT）敵手P在下面實驗中的優(yōu)勢AdvP是可忽略的，則稱方案具有INDIDCPA安全性：

1）模擬者O執(zhí)行Setup，將輸出值PK發(fā)送給P。

2）P進行多次用戶私鑰詢問，分別由ODer給出相應(yīng)回答。

3）P給出挑戰(zhàn)身份向量id=（id1，id2，…，idl），l≤d和消息m0，m1，O隨機選擇γ∈{0，1}，計算c=Enc（id，mγ）并發(fā)送給P。

4）P繼續(xù)進行多次用戶私鑰詢問（但要求私鑰詢問向量id′不能是id本身也不能是id的前綴），由預(yù)言機給出回答。

5）P輸出γ′∈{0，1}作為對γ的猜測，P的優(yōu)勢定義為：

AdvP=Pr[γ=γ′]-1/2

2HIBFHE方案

2.1方案描述

2.2解密正確性

在解密算法中，私鑰skid=v是密文矩陣C的近似特征向量， μ是密文矩陣的特征值，根據(jù)特征向量與特征值的性質(zhì)可得：xi ← 〈Ci，v〉=μ·vi+ei，這當中ei是噪聲向量e中的一個元素，可以忽略不計，對xi/vi取最近整數(shù)將正確地恢復出消息μ。

2.3同態(tài)加與同態(tài)乘操作

設(shè)在同一身份id下對消息μ1， μ2∈{0，1}加密得到的密文分別為C1，C2∈ZNq，下面將分析如何根據(jù)C1和C2來計算消息μ1+μ2和μ1·μ2的加密。

1）同態(tài)加。

add（C1，C2）：輸出Flatten（C1+C2），計算密文加法：

Add（C1，C2）·v=（C1+C2）·v=（μ1+μ2）·v+e1+e2

按照解密的計算形式，很容易看出其同態(tài)加之后的結(jié)果，只要滿足噪聲e1+e2

2）同態(tài)乘。

同樣按照解密的計算形式，只有在滿足噪聲μ2·e1+Ci·e2

文獻[9]中提出了一個密文校平技術(shù)，使得密文矩陣被嚴格控制在滿足同態(tài)計算性質(zhì)的界限內(nèi)，2.4節(jié)將詳細介紹這一技術(shù)。

2.4密文校平技術(shù)

3安全性及性能分析

3.1安全性分析

本文提出的HIBFHE方案的安全性基于LWE問題。下面給出定理2，將HIBFHE方案的語義安全性歸約到LWE問題。

定理2在LWE困難問題下，本文方案具有INDIDCPA安全性。H是隨機預(yù)言機，P是一個PPT敵手，定義QH為敵手P詢問預(yù)言機的次數(shù)，d是最大層次深度。B為判定LWE問題的PPT算法，將敵手P的優(yōu)勢定義為ε，則：

ε≤LWE此處的符號是減號？連字符？還是下劃線？請明確。adv[B]·（dQdH）+negl（n）

證明利用敵手P構(gòu)造一個優(yōu)勢為ε/dQdH的LWE算法B。

SetupB按如下過程為P設(shè)置模擬攻擊環(huán)境：

1）均勻地隨機選擇d個整數(shù)Q*1，Q*2，…，Q*d∈[QH]，其中QH是P能夠進行查詢最大次數(shù)。

2）通過運行R*i ← SampleR（1m），i=1，2，…，d生成d個m×m隨機矩陣R*1，R*2，…，R*d。

3）在給定的LWE實例下，通過聚合得到隨機矩陣A0∈Zn×mq。隨機選擇ω∈[d]，得到A ← A0R*ω…R*2R*1∈Zn×mq。

4）給出公開參數(shù)PP=（A， μ0）。

Secretkeyqueries敵手P可以適應(yīng)性地選擇任意身份id進行交互式私鑰查詢，B對滿足長度id=k∈[d]的查詢給出如下回答。

1）令j∈[k]作為滿足H（id/j）≠R*j的最淺層級，若出現(xiàn)H（id/j）=R*j， j=1，2，…，k的情形則查詢失敗。

2）構(gòu)造矩陣：

B=A·（R*1）-1…（R*j-1）-1·H（id/j）-1 mod q

TB是Λ⊥q（B）的一組短格基，得到skid/j=TB。

3）運行Derive（PP，TB，id）生成身份id對應(yīng)的私鑰skid，將這一結(jié)果發(fā)送給敵手P。

ChallengeP給出挑戰(zhàn)身份id*和消息b∈{0，1}，令l=id*，i∈[l]，在H（id*/i）=R*i且ω=l的條件下生成加密矩陣C′id*，運行Encrypt算法得到消息b的密文矩陣C，將結(jié)果發(fā)送給敵手P。P得到結(jié)果后仍然能夠繼續(xù)進行私鑰查詢，但要求私鑰詢問向量不能是id*本身也不能是id*的前綴。

GuessP根據(jù)所掌握的信息給出猜測b′，B輸出P的猜測并結(jié)束實驗，如果b′=b，則敵手攻擊成功。

由于公開參數(shù)的分配與實際系統(tǒng)中響應(yīng)私鑰查詢的回應(yīng)完全相同，而本實驗中通過隨機預(yù)言機H獲取的回應(yīng)也與實際系統(tǒng)中相同，所以在算法B不出現(xiàn)查詢失敗的情況下，挑戰(zhàn)密文的分布或者與實際系統(tǒng)中相同，或者是完全獨立且隨機取自（Zq，Zmq）的。因而在不出現(xiàn)查詢失敗的情況下，算法B在判定LWE問題上的優(yōu)勢與敵手P攻擊的優(yōu)勢相同。

將敵手P的優(yōu)勢定義為ε，則有：

LWEadv[B]≥[ε/（dQdH）]-negl（n）

可以得到AdvCPAP≤LWEadv[B]·（dQdH）+negl（n），解決LWE問題被公認為是困難的，所以認為敵手P攻擊成功的優(yōu)勢可忽略。

3.2性能分析

本文構(gòu)造了一個層次型全同態(tài)基于身份的加密方案，相較于文獻[12]中的半同態(tài)加密方案和文獻[11]中的類同態(tài)加密方案，明顯擴展了IBE方案的同態(tài)功能，使其性能得到了很大提升。

在現(xiàn)有的IBFHE方案范圍內(nèi)作效率分析。與文獻[14]中的方案—— CM（ClearMcgoldrick）方案進行比較，本文方案在構(gòu)造方法上更加自然和直觀，密文計算直接對應(yīng)到矩陣的加乘運算。本文方案在計算過程中不需要先用加密過的私鑰對密文進行同態(tài)解密，達到控制噪聲的目的之后，得到新鮮密文參與到下一層電路的計算，即不需要進行同態(tài)解密的操作。CM方案的噪聲在同態(tài)計算中將以兩級指數(shù)的形式增長，而本文方案因為運用了密文校平技術(shù)，當運行深度為L的布爾電路時，噪聲至多為（N+1）LB，可以更好地控制噪聲增長，結(jié)果如表1。

與GSW方案[9]進行比較，雖然使用了相同的轉(zhuǎn)化機制，但由于GSW方案中采用了CHKP10的IBE方案，而本文采用了ABB10b的IBE方案作為轉(zhuǎn)化對象，后者相較于前者在效率上具有很大提升，所以本文方案效率更高。下面從密文長度、密鑰長度以及格維數(shù)3個方面進行比較，結(jié)果如表2。

4結(jié)語

本文基于LWE問題，利用Gentry等[9]提出的全同態(tài)轉(zhuǎn)化機制，結(jié)合Agrawal等[15]提出的HIBE方案，構(gòu)造了一個新的HIBFHE方案，在隨機預(yù)言機模型下證明是INDIDCPA安全的。與半同態(tài)和類同態(tài)IBE方案相比，提升了方案的同態(tài)運算能力；與現(xiàn)有的IBFHE方案相比，構(gòu)造方法更加自然和直觀，經(jīng)過同態(tài)計算后密文維數(shù)不會增加，利用密文校平技術(shù)將噪聲控制在解密正確的范圍內(nèi)，具有更高的效率。

基于屬性的加密（ABE）作為IBE的擴展和延伸，把IBE中表示用戶身份的唯一標識，擴展成為由多個屬性組成的屬性集合，還將訪問結(jié)構(gòu)融入到屬性集合中，具備細粒度訪問控制的能力，更能適應(yīng)當前互聯(lián)網(wǎng)的發(fā)展需求。下一步將對具備同態(tài)性質(zhì)的ABE方案進行探索和研究。

參考文獻：

[1]

RIVEST R L， ADLEMAN L， DERTOUZOS M L. On data banks and privacy homomorphisms [J]. Foundations of Secure Computation， 1978， 4（11）： 169-180.

[2]

BENALOH J. Dense probabilistic encryption [C]// Proceedings of the 1994 Workshop on Selected Areas of Cryptography. Berlin： Springer， 1994： 120-128.

[3]

PAILLIER P. Publickey cryptosystems based on composite degree residuosity classes [C]// EUROCRYPT99： Proceedings of the 17th International Conference on Theory and Application of Cryptographic Techniques. Berlin： Springer， 1999： 223-238.

[4]

BONEH D， GOH E J， NISSIM K. Evaluating 2DNF formulas on ciphertexts [C]// TCC05： Proceedings of the Second International Conference on Theory of Cryptography. Berlin： Springer， 2005： 325-341.

[5]

GENTRY C. Fully homomorphic encryption using ideal lattices [C]// Proceedings of the 41st ACM Symposium on Theory of Computing. New York： ACM， 2009： 169-178.

[6]

VAN DIJK M， GENTRY C， HALEVI S， et al. Fully homomorphic encryption over the integers [C]// EUROCRYPT10： Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2010： 24-43.

[7]

SMART N P， VERCAUTEREN F. Fully homomorphic encryption with relatively small key and ciphertext sizes [C]// PKC10： Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography. Berlin： Springer， 2010： 420-443.

[8]

GENTRY C， HALEVI S， SMART N P. Fully homomorphic encryption with polylog overhead [C]// EUROCRYPT12： Proceedings of the 31st Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2012： 465-482.

[9]

GENTRY C， SAHAI A， WATERS B. Homomorphic encryption from learning with errors： conceptuallysimpler， asymptoticallyfaster， attributebased [C]// CRYPTO 2013： Proceedings of the 33rd Annual Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2013： 75-92.

[10]

SHAMIR A. Identitybased cryptosystems and signature schemes [C]// Proceedings of CRYPTO 84 on Advances in Cryptology. Berlin： Springer， 1984： 47-53.

[11]

GENTRY C， HALEVI S， VAIKUNTANATHAN V. A simple BGNtype cryptosystem from LWE [C]// EUROCRYPT10 Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2010： 506-522.

[12]

CLEAR M， HUGHES A， TEWARI H. Homomorphic encryption with access policies： characterization and new constructions [C]// AFRICACRYPT 2013： Proceedings of the 6th International Conference on Cryptology in Africa. Berlin： Springer， 2013： 61-87.

[13]

COCKS C. An identity based encryption scheme based on quadratic residues [C]// Proceedings of the 8th IMA International Conference on Cryptography and Coding. Berlin： Springer， 2001： 360-363.

[14]

CLEAR M， MCGOLDRICK C. Bootstrappable identitybased fully homomorphic encryption [C]// CANS 2014： Proceedings of 13th International Conference on Cryptology and Network Security. Berlin： Springer， 2014： 1-19.

[15]

AGRAWAL S， BONEH D， BOYEN X. Lattice basis delegation in fixed dimension and shorterciphertext hierarchical IBE [C]// CRYPTO 2010： Proceedings of the 30th Annual Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2010： 98-115.

[16]

REGEV O. On lattices， learning with errors， random linear codes， and cryptography [J]. Journal of the ACM， 2009， 56 （6）： Article No. 34.

[17]

BRAKERSKI Z， LANGLOIS A， PEIKERT C， et al. Classical hardness of learning with errors [C]// Proceedings of the 2013 Fortyfifth Annual ACM Symposium on Theory of Computing. New York： ACM， 2013： 575-584.