基于CPU多核的FHEW并行算法

Parallel FHEW Based on Multi-core CPU

全同态加密算法发展迅猛,然而效率低下仍是其无法实际应用的关键因素.为了进一步加快全同态加密算法的运行速度,本文针对EUROCRYPT 2015上全同态加密算法FHEW存在大量独立矩阵和向量运算,以及CPU多核适合大量独立数据的运算的特点,提出并实现了FHEW方案的CPU多核并行算法.首先,通过分析比较FHEW算法四个主要过程的特点和运行时间,发现该算法中最消耗时间是密钥生成过程和同态与非门电路(包含自举过程),并且该两个过程中涉及大量独立的矩阵和向量运算.所以,本文对这两个过程进行了CPU多核并行优化.其次,考虑到算法中存在大量离散傅立叶变换和逆变换,该变换和逆变换消耗大量时间和内存资源,本文对离散傅立叶变换和逆变换函数中的大部分过程进行并行计算,从而提升了离散傅立叶函数的运行速度,进一步提高了方案效率.最后,分别运行原始算法和并行算法18次,得到平均运行时间.实验结果表明,在相同的环境下,密钥生成算法的运行时间由13029ms降至2434 ms,效率提高了4.35倍;一次同态与非门电路运算的运行时间由298.5 ms降至81 ms,效率提高了2.68倍.

Fully homomorphic encryption algorithm is developing rapidly, but it still can not be applied because of its inefficiency. In order to speed up the operation speed of the full homomorphic encryption algorithm FHEW, the parallel algorithm of FHEW scheme is proposed to accelerate the speed of fully homomorphic encryption. This study finds the characteristics that FHEW involves a large number of independent matrix and vector operations, and multi-core CPU fits for the calculation of mass of independent date. First of all, by analyzing and comparing the characteristics and running time of the four main processes of FHEW algorithm, we find that most time-consuming processes in the algorithm are the key generation process and the homomorphism NAND gate(including the bootstrap process), and the two processes involve a large number of independent matrix and vector operations. Secondly, considering that there are a large number of discrete Fourier transform and inverse transform in the algorithm, these transform and inverse transform consume a large amount of time and memory resources. In this study, most of the discrete Fourier transform and inverse transform function are calculated in parallel, which improves discrete Fourier transform function speed, to further improve the program efficiency. Finally, the original algorithm and parallel algorithm are run 18 times respectively to get the average running time. Experimental results show that, the running time of the key generation algorithm is reduced from 13029 ms to 2434 ms and the efficiency is improved by 4.35 times. The running time of a homomorphism and NAND gate operation is reduced from 298.5 ms to 81 ms, which improves the efficiency 2.68 times.