基于容错学习的GSW型全同态层次型IBE方案.docVIP

基于容错学习的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]首次提出