基于CPU多核的FHEW并行算法

摘要

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