基于容錯學習的GSW型全同態層次型IBE方案

戴曉明 張薇 鄭志恒 李鎮林

摘要：針對傳統的基于身份的加密（IBE）方案不能夠對密文直接進行計算這一功能上的缺陷，提出了一個新的IBE方案。該方案利用Gentry等提出的同態轉化機制，結合Agrawal等構造的層次型IBE方案，構造了一個具有全同態性質的層次型IBE方案。與Gentry等提出的全同態加密（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等提出的全同態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）相比，該方案構造方法更加自然，空間復雜度由立方級降低到平方級，效率更高。在當前云計算背景下，有助于基于容錯學習（LWE）的全同態加密方案從理論向實踐轉化。通過性能分析并在隨機預言機模型下驗證了所提方案具有完全安全下的選擇明文攻擊（INDIDCPA）安全性。

關鍵詞：

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

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

0引言

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

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

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

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

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

1相關基礎理論

1.1LWE問題和GvpSAP

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義4全同態加密。如果對于所有的算術電路類，方案都具有同態性質，則稱方案為全同態加密方案。

1.3HIBE方案及安全模型

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

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

在下面的描述中，設k為安全參數。以ODer表示模擬用戶密鑰產生算法的預言機。

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

1）模擬者O執行Setup，將輸出值PK發送給P。

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

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

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

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

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

2HIBFHE方案

2.1方案描述

2.2解密正確性

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

2.3同態加與同態乘操作

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

1）同態加。

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

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

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

2）同態乘。

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

文獻[9]中提出了一個密文校平技術，使得密文矩陣被嚴格控制在滿足同態計算性質的界限內，2.4節將詳細介紹這一技術。

2.4密文校平技術

3安全性及性能分析

3.1安全性分析

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

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

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

證明利用敵手P構造一個優勢為ε/dQdH的LWE算法B。

SetupB按如下過程為P設置模擬攻擊環境：

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

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）給出公開參數PP=（A， μ0）。

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

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

2）構造矩陣：

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對應的私鑰skid，將這一結果發送給敵手P。

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

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

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

將敵手P的優勢定義為ε，則有：

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

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

3.2性能分析

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

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

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

4結語

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

基于屬性的加密（ABE）作為IBE的擴展和延伸，把IBE中表示用戶身份的唯一標識，擴展成為由多個屬性組成的屬性集合，還將訪問結構融入到屬性集合中，具備細粒度訪問控制的能力，更能適應當前互聯網的發展需求。下一步將對具備同態性質的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.