高效的身份基多用戶全同態(tài)加密方案

涂廣升 楊曉元 周潭平

摘 要：針對傳統(tǒng)的身份基全同態(tài)加密（Identity-Based Fully Homomorphic Encryption，IBFHE）方案無法對不同身份標(biāo)識（IDentity，ID）下的密文進(jìn)行同態(tài)運算的問題，提出一個基于誤差學(xué)習(xí)（Learning With Error，LWE）問題的分層身份基多用戶全同態(tài)加密方案。該方案利用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年提出的身份基多用戶全同態(tài)加密方案（[CM15]方案）的轉(zhuǎn)化機(jī)制，結(jié)合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]方案），實現(xiàn)了不同身份標(biāo)識下的密文同態(tài)運算，應(yīng)用前景更加廣闊，在隨機(jī)預(yù)言機(jī)模型下為基于身份匿名的選擇明文攻擊下的不可區(qū)分性（IND-ID-CPA）安全。與[CM15]方案相比，該方案在公鑰規(guī)模、私鑰規(guī)模、密文尺寸、分層性質(zhì)和密鑰更新周期方面都具有優(yōu)勢。

關(guān)鍵詞：分層身份基加密;多用戶;全同態(tài)加密;同態(tài)運算;基于誤差學(xué)習(xí)

中圖分類號： TP309

文獻(xiàn)標(biāo)志碼：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]提出了第一個基于理想格的全同態(tài)加密方案，全同態(tài)加密得到了越來越多密碼學(xué)家的關(guān)注。此后，新的全同態(tài)加密方案相繼出現(xiàn)，其中基于理想格的全同態(tài)加密方案（如[GH11b]方案[2]）、基于環(huán)上的誤差學(xué)習(xí)問題的全同態(tài)加密方案（如[BGV12]方案[3]）、運用特征向量法的全同態(tài)加密方案（如[GSW13]方案[4]）成為研究的熱點，同態(tài)加密的效率也在不斷提高。

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

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

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

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

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

1.1 全同態(tài)加密

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

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

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

1.2 分層身份加密（HIBE）

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

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

Lower-level Setup 用戶根據(jù)身份信息設(shè)置自己的低層密鑰，用于生成下一層身份信息對應(yīng)的私鑰。

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

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

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

1.3 LWE問題

LWE問題最早由Regev[13]在2005年提出，已經(jīng)被證明為一個難解的多項式復(fù)雜程度的非確定性（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），就存在一個有效的經(jīng)典算法，能夠解決近似因子為（nq/B）的GapSVP問題。

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

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

2 分層身份基多用戶全同態(tài)加密方案

2.1 屏蔽系統(tǒng)

由文獻(xiàn)[4]的轉(zhuǎn)化機(jī)制可知，一個IBE方案可以被轉(zhuǎn)化為IBFHE方案，如果滿足以下三條性質(zhì)[4]：

為了將身份基全同態(tài)加密方案轉(zhuǎn)化為身份基多用戶全同態(tài)加密方案，應(yīng)當(dāng)為IBE方案構(gòu)造一個相應(yīng)的屏蔽系統(tǒng)，并滿足其正確性和安全性。

2.2 本文身份基多用戶全同態(tài)加密方案

利用文獻(xiàn)[6]的轉(zhuǎn)化機(jī)制，對RO模型下的[CHKP10]方案構(gòu)造相應(yīng)的屏蔽系統(tǒng)MS[CHKP10]，從而得到一個新的身份基多用戶全同態(tài)加密方案，表示為mHIBFHE，具體方案如下。

3 方案分析

3.1 正確性分析

3.2 安全性分析

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

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

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

1）選定攻擊目標(biāo)身份ID*。

2）初始化參數(shù)設(shè)置：挑戰(zhàn)者運行Setup算法，得到系統(tǒng)公共參數(shù)，并公開給攻擊者A，并保留主密鑰。

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

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

5）由以上結(jié)論可知，MS[CHKP10]在隨機(jī)預(yù)言機(jī)模型下為IND-ID-CPA安全，文獻(xiàn)[7]已經(jīng)證明[CHKP10]方案在隨機(jī)預(yù)言機(jī)模型下為IND-ID-CPA安全，因此，本方案為隨機(jī)預(yù)言機(jī)模型下IND-ID-CPA安全。

3.3 性能分析

本文構(gòu)造了一個基于LWE問題的高效分層身份基多用戶全同態(tài)加密方案，與其他方案相比，應(yīng)用場景更廣，效率更高，具體表現(xiàn)在以下幾個方面：

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

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

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

4 結(jié)語

本文基于LWE問題，利用[CM15]方案中的轉(zhuǎn)化機(jī)制，結(jié)合[CHKP10]方案，構(gòu)造了一個高效的分層身份基多用戶全同態(tài)加密方案，并證明了該方案為隨機(jī)預(yù)言機(jī)模型下的IND-ID-CPA安全。通過對比分析，本方案應(yīng)用場景更廣、效率更高。

與身份加密相比，屬性加密（ABE）能夠?qū)崿F(xiàn)更細(xì)粒度的訪問控制和一對多的加解密[17]。后續(xù)工作將研究多密鑰全同態(tài)加密方案與屬性加密的結(jié)合，實現(xiàn)屬性基多用戶全同態(tài)加密方案。

參考文獻(xiàn) （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] 陳智罡.基于格的全同態(tài)加密研究與設(shè)計[D].南京：南京航空航天大學(xué)，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] 李增鵬，馬春光，周紅生.全同態(tài)加密研究[J].密碼學(xué)報， 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問題的密碼體制研究與設(shè)計[D].西安：武警工程大學(xué)，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] 石悅，李相龍，戴方芳.一種基于屬性基加密的增強(qiáng)型軟件定義網(wǎng)絡(luò)安全框架[J].信息網(wǎng)絡(luò)安全，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.）