高效的身份基多用户全同态加密方案

涂广升 杨晓元 周潭平

摘 要：針对传统的身份基全同态加密（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.）