基于环上容错学习和GSW的层次型全同态加密方案

来源：计算机应用杂志2016年第4期北京时间：

作者：王曌, 丁勇, 王会勇

单位：1. 桂林电子科技大学 数学与计算科学学院, 广西 桂林 541004;2. 桂林电子科技大学 广西信息科学实验中心, 广西 桂林 541004;3. 中国科学院 成都计算机应用研究所, 四川 成都 610041

摘要：针对目前全同态加密方案效率不高的问题,对GSW同态加密方案进行改进,提出基于环上容错学习和GSW的层次型全同态加密方案。首先,构造基于环上容错学习困难问题的基本公钥加密方案,利用近似特征向量方法使其具有加法、乘法同态性,进一步为简化噪声增长过程的分析而引入随机化函数技术;其次,证明了基本加密方案的正确性、安全性,并详细分析了同态加法、同态乘法和同态与非门操作的正确性;最后,根据密文对应噪声项的增长情况及困难问题的安全性设置方案安全参数,并利用快速傅里叶变换降低多项式乘法运算的计算复杂度,构造出层次型(Leveled)全同态加密方案。与GSW方案相比,新方案具有更小的公钥尺寸,且同态计算每个与非门的复杂度从Õ((nL)2.37)降低到Õ(nL2)。

关键词：全同态加密,环上容错学习,随机化函数,噪声增长,层次型全同态

基金资助：广西自然科学基金资助项目(2013GXNSFBB053005);广西科学研究与技术开发计划项目(14124004-4-10);广西研究生教育创新计划项目(XJYC2012020);广西信息科学实验中心项目(2015-12)。