马　飞，李　娟

(1．北方民族大学 计算机科学与工程学院， 宁夏 银川 750021;2．合肥工业大学 计算机与信息学院，安徽 合肥 230009)



几种重要FHE加密结构的深入研究与分析*

马飞1,2，李娟1

(1．北方民族大学 计算机科学与工程学院， 宁夏 银川 750021;2．合肥工业大学 计算机与信息学院，安徽 合肥 230009)

摘要：对当前几种重要的全同态加密结构的构造原理及性质进行了深入剖析，重点对FHE加解密算法、算法基于的难题假设、算法复杂度、密钥特征、密文扩展性等特点进行了深入分析与详细比较，并针对结构中的不足之处提出了改进与优化建议，为进一步对FHE结构优化提供借鉴。最后对全同态加密的应用前景进行了全面展望。

关键词：全同态加密；结构比较；云计算；LWE/RLWE

0引言

Rivest等人在上世纪70年代末引入了称为“隐私同态”的概念[1]，在该加密结构的构想下，能允许在密文域中做任意操作，而无需进行解密。随后的研究人员提出了一些操作受限的称之为“半同态”的加密结构，如RSA加密算法[2]与ElGamal加密算法[3-4]是具有任意次乘法运算的乘法同态性加密结构，而其加法运算不具有同态性。Paillier算法[5]与Bresson 等人提出的加密算法具有加法同态性，不具有乘法同态性。而Boneh-Goh-Nissim加密算法[6]支持任意次数的加法运算，但只持一次乘法运算，该算法是最接近于全同态的加密结构之一。直到2009年，IBM公司的Graig Gentry在欧密会上发表了一篇名为《基于理想格的全同态加密》的文章，这一被命名为“全同态加密”(Fully Homomorphic Encryption,FHE)的技术被冠以密码学“圣杯”的称号，成为了密码学最新的研究热点。……