涂廣升 楊曉元 周潭平

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

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

中圖分類(lèi)號(hào)： TP309

文獻(xiàn)標(biāo)志碼：A

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

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

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

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

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

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

1.1 全同態(tài)加密

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

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

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

1.2 分層身份加密（HIBE）

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

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

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

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

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

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

1.3 LWE問(wèn)題

LWE問(wèn)題最早由Regev[13]在2005年提出，已經(jīng)被證明為一個(gè)難解的多項(xiàng)式復(fù)雜程度的非確定性（Non-deterministic Polynomial， NP）問(wèn)題。

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

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

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

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

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

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

2.1 屏蔽系統(tǒng)

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

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

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

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

3 方案分析

3.1 正確性分析

3.2 安全性分析

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

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

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

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

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

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

4）由于解決判定性LWE問(wèn)題是困難的，因此，攻擊者無(wú)法區(qū)分游戲G0和G1的分布，即攻擊者無(wú)法區(qū)分bη和bj的兩種分布。因此，將通用信息U返回給攻擊者，攻擊者即使詢(xún)問(wèn)隨機(jī)預(yù)言機(jī)也無(wú)法區(qū)分U的分布，無(wú)法得出任何關(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)造了一個(gè)基于LWE問(wèn)題的高效分層身份基多用戶(hù)全同態(tài)加密方案，與其他方案相比，應(yīng)用場(chǎng)景更廣，效率更高，具體表現(xiàn)在以下幾個(gè)方面：

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

2）與[GSW13]方案提出的HIBFHE方案相比，將方案的應(yīng)用場(chǎng)景由單用戶(hù)擴(kuò)展到多用戶(hù)，實(shí)現(xiàn)了不同用戶(hù)之間密文的同態(tài)計(jì)算。同態(tài)加法和乘法可以通過(guò)Zq上矩陣的平凡加法和乘法運(yùn)算實(shí)現(xiàn)上的加法乘法運(yùn)算，效率更高，密文運(yù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)勢(shì)，并且實(shí)現(xiàn)了分層功能，因此，在安全性相同（都能達(dá)到RO模型下的選擇安全）的情況下，本方案的密鑰更新時(shí)間相對(duì)更短、效率更高。具體分析見(jiàn)表1、表2。

4 結(jié)語(yǔ)

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

與身份加密相比，屬性加密（ABE）能夠?qū)崿F(xiàn)更細(xì)粒度的訪問(wèn)控制和一對(duì)多的加解密[17]。后續(xù)工作將研究多密鑰全同態(tài)加密方案與屬性加密的結(jié)合，實(shí)現(xiàn)屬性基多用戶(hù)全同態(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è)計(jì)[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é)報(bào)， 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問(wèn)題的密碼體制研究與設(shè)計(jì)[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.）