高效的身份基多用戶全同態加密方案

涂廣升 楊曉元 周潭平

摘 要：針對傳統的身份基全同態加密（Identity-Based Fully Homomorphic Encryption，IBFHE）方案無法對不同身份標識（IDentity，ID）下的密文進行同態運算的問題，提出一個基于誤差學習（Learning With Error，LWE）問題的分層身份基多用戶全同態加密方案。該方案利用Clear等（CLEAR M， McGOLDRICK C. Multi-identity and multi-key leveled FHE from learning with errors. Proceedings of the 2015 Annual Cryptology Conference， LNCS 9216. Berlin： Springer， 2015： 630-656）在2015年提出的身份基多用戶全同態加密方案（[CM15]方案）的轉化機制，結合Cash等（CASH D， HOFHEINZ D， KILTZ E， et al. Bonsai trees， or how to delegate a lattice basis. Proceedings of the 2010 Annual International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 6110. Berlin： Springer， 2010： 523-552）在2010年提出的身份基加密（Identity-Based Encryption，IBE）方案（[CHKP10]方案），實現了不同身份標識下的密文同態運算，應用前景更加廣闊，在隨機預言機模型下為基于身份匿名的選擇明文攻擊下的不可區分性（IND-ID-CPA）安全。與[CM15]方案相比，該方案在公鑰規模、私鑰規模、密文尺寸、分層性質和密鑰更新周期方面都具有優勢。

關鍵詞：分層身份基加密;多用戶;全同態加密;同態運算;基于誤差學習

中圖分類號： TP309

文獻標志碼：A

文章編號：1001-9081（2019）03-0750-06

Abstract： Focusing on the issue that the traditional Identity-Based Fully Homomorphic Encryption scheme （IBFHE） cannot perform homomorphic operations on ciphertexts under different IDentities （ID）， a hierarchical identity-based multi-identity fully homomorphic encryption scheme based on Learning With Error （LWE） problem was proposed. In the proposed scheme， the transformation mechanism of identity-based multi-identity homomorphic encryption scheme （[CM15] scheme） proposed by Clear et al. （CLEAR M， McGOLDRICK C. Multi-identity and multi-key leveled FHE from learning with errors. Proceedings of the 2015 Annual Cryptology Conference， LNCS 9216. Berlin： Springer， 2015： 630-656） in 2015 was combined with Identity-Based Encryption （IBE） scheme proposed by Cash et al. （CASH D， HOFHEINZ D， KILTZ E， et al. Bonsai trees， or how to delegate a lattice basis. Proceedings of the 2010 Annual International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 6110. Berlin： Springer， 2010： 523-552） in 2010 （[CHKP10] scheme）， guranteeing IND-ID-CPA （INDistinguishability of IDentity-based encryption under Chosen-Plaintext Attack） security in the random oracle model and realizing ciphertext homomorphic operation under different identities， so the application of this scheme was more promising. Compared with [CM15] scheme， the proposed scheme has advantages in terms of public key scale， private key scale， ciphertext size， and hierarchical properties， and has a wide application prospect.

Key words： hierarchical identity-based encryption; multi-identity; fully homomorphic encryption; homomorphic operation; Learning With Error （LWE）

0 引言

2009年，Gentry[1]提出了第一個基于理想格的全同態加密方案，全同態加密得到了越來越多密碼學家的關注。此后，新的全同態加密方案相繼出現，其中基于理想格的全同態加密方案（如[GH11b]方案[2]）、基于環上的誤差學習問題的全同態加密方案（如[BGV12]方案[3]）、運用特征向量法的全同態加密方案（如[GSW13]方案[4]）成為研究的熱點，同態加密的效率也在不斷提高。

全同態加密方案有多種分類方式，如果以同態運算能夠執行的電路深度為依據，全同態加密方案可分為“純”的全同態加密方案和層次型全同態加密方案[5]。前者可以對任意深度的電路作任意的運算。層次型全同態加密方案只能執行深度為 L的計算電路，方案的參數選擇依賴于 L。雖然它并不能達到任意深度電路的要求，但對于多項式深度的電路，在滿足用戶需求的同時，更加高效實用。

在身份基加密方案中，身份信息作為用戶的唯一標識，用戶的公鑰可以從用戶的身份信息字符串和系統的公共參數中獲得，對應的私鑰為用戶私有。2013年Gentry等[4]提出了一個新的層次型全同態加密方案。該方案允許計算方在不獲得用戶的計算密鑰（EValuation Key， EVK），而只需要知道系統公共參數信息的情況下，實現對明文的加密和對密文的運算。利用此特性，該方案構造了第一個身份基全同態加密方案;然而它只適用于單用戶身份信息場景，即只能對在同一身份信息下加密的密文進行運算。2015年，Clear等[6]通過構造屏蔽系統（Masking System， MS）的方法，提出了第一個基于誤差學習（Learning With Error， LWE）問題的身份基多用戶全同態加密方案（該方案稱為[CM15]方案），并證明該方案在隨機預言機模型下為IND-ID-CPA（INDistinguishability of IDentity-based encryption under Chosen-Plaintext Attack）安全。

身份基多用戶全同態加密方案實現了不同用戶密文之間的同態運算，在密文計算領域有著廣泛的應用。以兩方的密文計算為例，假設C為可信任的權威機構， Alice和Bob為C中的兩個不同身份體或不同部門，其身份信息分別為a，b。C為Alice和Bob產生公開的公鑰信息，并分配相應的私鑰。公共用戶可以分別使用Alice和Bob的公開身份信息和公共參數對個人信息進行加密，而后將密文分別發送給Alice和Bob。C將數據上傳到半透明的云服務器E，在服務器端進行同態運算，得到新的密文，而后返回給C。權威機構C通過多方計算協議（Multi-Party Computation， MPC），使用Alice和Bob的私鑰對密文進行解密，解密后的結果保持同態方案的性質。整個過程中既實現了不同身份信息下密文的同態運算，也能保證用戶之間的私鑰信息的非交互性，即Alice和Bob互相不知道對方的私鑰。這里的實例場景表示不同身份信息的用戶數κ=2，對于更多不同身份信息用戶的情況同樣適用。

本文利用文獻[6]的轉化機制，結合Cash等[7]提出的分層身份基加密（Hierarchical Identity-Based Encryption，HIBE）方案（該方案被稱為[CHKP10]方案），將該方案轉化為分層身份基多用戶全同態加密方案。相比于傳統的身份基全同態加密方案，本方案實現了對不同身份信息下密文的同態運算，能夠更好地與其他技術結合（如即時多方計算協議、奇點打孔陷門），應用場景更加廣泛。相比于文獻[6]中的身份基多用戶全同態加密方案，本方案雖然使用相同的轉化機制，但本方案采用隨機預言機模型下的[CHKP10]方案，文獻[6]采用Gentry等[8]在2008年發表的利用陷門函數構造的身份基加密方案（該方案被稱為 [GPV08]方案）。由于RO模型下的[CHKP10]方案相比[GPV08]方案在公鑰規模、私鑰規模、密文尺寸方面都有一定優勢，并且實現了分層功能，因此，在安全性相同（都能達到隨機預言機（Random Oracle，RO）模型下的選擇安全）的情況下，本方案的密鑰更新時間更短，效率更高。

1 相關理論基礎

1.1 全同態加密

全同態加密方案包含四個算法，分別為密鑰生成算法、加密算法、解密算法和密文計算算法[1，9]。

緊湊性 解密電路的深度并不隨著計算電路深度的增加而增加，也就是說計算電路產生的密文大小并不取決于計算電路的大小。

定義1 層次型全同態加密方案。對于任意L∈Z+，一個同態加密方案ε（L）能夠計算的電路深度為L，并且滿足上述的緊湊性。設電路大小用z表示，緊湊計算的復雜度為poly（λ，L，z），則稱該方案為層次型全同態方案[10]。

1.2 分層身份加密（HIBE）

HIBE是在IBE的基礎上發展起來的，在密鑰生成階段能夠很好地減輕私鑰生成器（Private Key Generator，PKG）的工作負擔。與IBE方案[11-12]（由Setup、KeyGen、Enc、Dec這4個算法組成）相比，HIBE方案有一個新的算法：Lower-level Setup算法。

Setup 輸入安全參數k，輸出主私鑰（MaSter Key， MSK）和公共參數（Public Parameters， PP）。主密鑰MSK為根PKG私有;PP為公共參數，包含用于生成身份信息對應的公鑰和密文空間描述等信息。

Lower-level Setup 用戶根據身份信息設置自己的低層密鑰，用于生成下一層身份信息對應的私鑰。

Key generation 輸入（PP，MSK，ID），PKG生成身份信息對應的私鑰sID。這里的PKG既可能是根PKG，也可能是身份信息對應的上一層的PKG。

Encryption 輸入（PP，ID，m），輸出密文c。其中PP來自根PKG，ID為低層接收方的身份信息，這樣可保證發送方不必知道低層用戶的密鑰參數。

Decryption 接收方根據來自根PKG的公共參數PP、用戶自己的身份信息對應的私鑰解密密文，解密密文得到相應的m。

1.3 LWE問題

LWE問題最早由Regev[13]在2005年提出，已經被證明為一個難解的多項式復雜程度的非確定性（Non-deterministic Polynomial， NP）問題。

定理1 令n為格的維度，q=q（n）， χ為B有界的高斯分布，B≥ω（log n）·n，如果存在一個有效的算法能夠解決平均情況下的LWE問題，那么[14]：

1）對于任意維度的格，存在一個有效的量子算法，能夠解決近似因子為（nq/B）的具有間隙的最短向量（Gap Version of Shortest Vector Problem， GapSVP）問題。

2）對于任意維度的格，如果q=q（n）≥（2n2），就存在一個有效的經典算法，能夠解決近似因子為（nq/B）的GapSVP問題。

利用量子歸約和經典歸約的方法，將LWE問題歸約到最壞情況下格上困難問題，而格的困難問題已經被證明為難解的NP問題。

Regev [15]在2010年給出證明，如果存在一個算法能夠以指數級別接近于1的概率解決判定性LWE問題，那么就存在一個更加高效的算法，能以指數級別接近于1的概率解決計算性LWE問題。即解決判定性LWE問題的優勢不大于解決LWE問題的優勢[16]。

2 分層身份基多用戶全同態加密方案

2.1 屏蔽系統

由文獻[4]的轉化機制可知，一個IBE方案可以被轉化為IBFHE方案，如果滿足以下三條性質[4]：

為了將身份基全同態加密方案轉化為身份基多用戶全同態加密方案，應當為IBE方案構造一個相應的屏蔽系統，并滿足其正確性和安全性。

2.2 本文身份基多用戶全同態加密方案

利用文獻[6]的轉化機制，對RO模型下的[CHKP10]方案構造相應的屏蔽系統MS[CHKP10]，從而得到一個新的身份基多用戶全同態加密方案，表示為mHIBFHE，具體方案如下。

3 方案分析

3.1 正確性分析

3.2 安全性分析

定理2 假設LWE問題是安全的，對于所有的多項式時間攻擊者A，在IND-ID-CPA游戲中成功區分μ0和μ1的概率可以忽略不計，那么MS[CHKP10]方案可以達到IND-ID-CPA安全性。

定理4 由文獻[7]可知，[CHKP10]方案在RO模型下為IND-ID-CPA安全。假設LWE問題是困難的，那么上述身份基多用戶全同態加密方案至少能夠達到隨機預言機模型下的IND-ID-CPA安全。

證明 方案的安全性可通過以下攻擊者A和挑戰者C游戲來定義：

1）選定攻擊目標身份ID*。

2）初始化參數設置：挑戰者運行Setup算法，得到系統公共參數，并公開給攻擊者A，并保留主密鑰。

3）假設有一個判別器D，以一個不可忽略的概率成功判別游戲G0和G1的分布，那么存在一個算法B可以利用判別器的輸出結果來解決一個實例化的判定性LWE問題。

4）由于解決判定性LWE問題是困難的，因此，攻擊者無法區分游戲G0和G1的分布，即攻擊者無法區分bη和bj的兩種分布。因此，將通用信息U返回給攻擊者，攻擊者即使詢問隨機預言機也無法區分U的分布，無法得出任何關于b的有用信息。

5）由以上結論可知，MS[CHKP10]在隨機預言機模型下為IND-ID-CPA安全，文獻[7]已經證明[CHKP10]方案在隨機預言機模型下為IND-ID-CPA安全，因此，本方案為隨機預言機模型下IND-ID-CPA安全。

3.3 性能分析

本文構造了一個基于LWE問題的高效分層身份基多用戶全同態加密方案，與其他方案相比，應用場景更廣，效率更高，具體表現在以下幾個方面：

1）與[CHKP10]方案相比，將一個簡單的HIBE方案擴展為multi-identity HIBFHE方案，應用前景更加廣闊，實現功能更加多樣。

2）與[GSW13]方案提出的HIBFHE方案相比，將方案的應用場景由單用戶擴展到多用戶，實現了不同用戶之間密文的同態計算。同態加法和乘法可以通過Zq上矩陣的平凡加法和乘法運算實現上的加法乘法運算，效率更高，密文運算后維度不變。并利用[GSW13]方案的校平技術，將噪聲控制在ω（κN+1）LB之內，保證了解密的正確性。

3）與[CM15]方案相比，本方案雖然使用相同的轉化機制，但本方案采用的身份基方案為隨機預言機模型下的[CHKP10]方案，而[CM15]方案采用[GPV08]方案。由于RO模型下的[CHKP10]方案相比[GPV08]方案在公鑰規模、私鑰規模、密文尺寸方面都有一定優勢，并且實現了分層功能，因此，在安全性相同（都能達到RO模型下的選擇安全）的情況下，本方案的密鑰更新時間相對更短、效率更高。具體分析見表1、表2。

4 結語

本文基于LWE問題，利用[CM15]方案中的轉化機制，結合[CHKP10]方案，構造了一個高效的分層身份基多用戶全同態加密方案，并證明了該方案為隨機預言機模型下的IND-ID-CPA安全。通過對比分析，本方案應用場景更廣、效率更高。

與身份加密相比，屬性加密（ABE）能夠實現更細粒度的訪問控制和一對多的加解密[17]。后續工作將研究多密鑰全同態加密方案與屬性加密的結合，實現屬性基多用戶全同態加密方案。

參考文獻 （References）

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

[2] GENTRY C， HALEVI S. Implementing Gentry's fully-homomorphic encryption scheme [C]// EUROCRYPT 2011： Proceedings of the 2011 Annual International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 6632. Berlin： Springer， 2011： 129-148.

[3] BRAKERSKI Z， GENTRY C， VAIKUNTANATHAN V. （Leveled） fully homomorphic encryption without bootstrapping [C]// ITCS '12： Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. New York： ACM， 2012： 309-325.

[4] GENTRY C， SAHAI A， WATERS B. Homomorphic encryption from learning with errors： conceptually-simpler， asymptotically-faster， attribute-based [C]// CRYPTO 2013： Proceedings of the 2013 Advances in Cryptology， LNCS 8042. Berlin： Springer， 2013： 75-92.

[5] 陳智罡.基于格的全同態加密研究與設計[D].南京：南京航空航天大學，2015：23.（CHEN Z G. Research and dedign of fully homomorphic encryption based on lattice [D]. Nanjing： Nanjing University of Aeronautics and Astronautics， 2015： 23.）

[6] CLEAR M， McGOLDRICK C. Multi-identity and multi-key leveled FHE from learning with errors [C]// Proceedings of the 2015 Annual Cryptology Conference， LNCS 9216. Berlin： Springer， 2015： 630-656.

[7] CASH D， HOFHEINZ D， KILTZ E， et al. Bonsai trees， or how to delegate a lattice basis [C]// Proceedings of the 2010 Annual International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 6110. Berlin： Springer， 2010： 523-552.

[8] GENTRY C， PEIKERT C， VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions [C]// STOC '08： Proceedings of the 40th Annual ACM Symposium on Theory of Computing. New York： ACM， 2008： 197-206.

[9] 李增鵬，馬春光，周紅生.全同態加密研究[J].密碼學報， 2017，4（6）：561-578.（LI Z P， MA C G， ZHOU H S. Overview on fully homomorphic encryption [J]. Journal of Cryptologic Research， 2017， 4（6）： 561-578.）

[10] MICCIANCIO D. Generalized compact knapsacks， cyclic lattices， and efficient one-way functions [J]. Computational Complexity， 2007， 16（4）： 365-411.

[11] BONEH D， FRANKLIN M. Identity-based encryption from the Weil pairing [C]// Proceedings of the 2001 Annual International Cryptology Conference， LNCS 2139. Berlin： Springer， 2001： 213-229.

[12] SHAMIR A. Identity-based cryptosystems and signature schemes [C]// Proceedings of the 1984 Workshop on the Theory and Application of Cryptographic Techniques， LNCS 196. Berlin： Springer， 1984： 47-53.

[13] REGEV O. On lattices， learning with errors， random linear codes， and cryptography [C]// Proceedings of the 37th Annual ACM Symposium on Theory of Computing. New York： ACM， 2005： 84-93.

[14] PEIKERT C. Public-key cryptosystems from the worst-case shortest vector problem： extended abstract [C]// STOC '09： Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York： ACM， 2009： 333-342.

[15] REGEV O. The learning with errors problem （invited survey） [C]// Proceedings of the 2010 IEEE 25th Annual Conference on Computational Complexity. Piscataway， NJ： IEEE， 2010： 191-204.

[16] 周潭平.基于GLWE問題的密碼體制研究與設計[D].西安：武警工程大學，2014：13.（ZHOU T P. Research and design of cryptosystem based on GLWE problem [D]. Xi'an： Engineering University of the Chinese People's Armed Police Force， 2014：13.）

[17] 石悅，李相龍，戴方芳.一種基于屬性基加密的增強型軟件定義網絡安全框架[J].信息網絡安全，2018（1）：15-22.（SHI Y， LI X L， DAI F F. An enhanced security framework of software defined network based on attribute-based encryption [J]. Netinfo Security， 2018（1）： 15-22.）