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

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

Leveled fully homomorphic encryption scheme based on Ring-LWE-GSW

Focusing on the issue that current fully homomorphic encryption schemes are not practical, Gentry-Sahai-Waters (GSW) homomorphic encryption scheme was improved and a leveled fully homomorphic encryption scheme based on Ring Learning with Error (Ring-LWE) and GSW was proposed. Firstly, a basic public key encryption scheme was constructed on Ring-LWE problem, the approximate eigenvector method was used to make it have homomorphic addition and multiplication properties, and the randomized function technique was introduced to simplify the analysis of noise blow-up. Secondly, the correctness and security of the proposed scheme was proved, the correctness of homomorphic addition, multiplication and NAND operation was analyzed in detail. Finally, security parameter was set in accordance with the noise blow-up with homomorphic evaluation and the security of Ring-LWE problem, fast Fourier transformation was adopted to reduce the computational complexity of polynomial multiplication, then a leveled fully homomorphic encryption scheme was given. The size of the pubic key in new scheme is shorter than that in GSW and the computational complexity of NAND gate is reduced from Õ((nL)^2.37) to Õ(nL²).