Accelerating Polynomial Multiplication for Homomorphic Encryption on GPUs
Accelerating Polynomial Multiplication for Homomorphic Encryption on GPUs
复制标题
DOI：
10.1109/seed55351.2022.00013
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Kaustubh Shivdikar;Gilbert Jonatan;Evelio Mora;Neal Livesay;R. Agrawal;Ajay Joshi;José L. Abellán;John Kim;D. Kaeli
中科院分区：
文献类型：
--
作者：
Kaustubh Shivdikar;Gilbert Jonatan;Evelio Mora;Neal Livesay;R. Agrawal;Ajay Joshi;José L. Abellán;John Kim;D. Kaeli
同态加密(HE)使用户能够安全地将敏感数据的存储和计算外包给不受信任的服务器。HE不仅为云系统的安全提供了一个有吸引力的解决方案，而且基于网格的HE系统也被认为可以抵抗量子计算机的攻击。然而，当前的HE实施存在高得令人望而却步的延迟。为了使基于格的HE在现实系统中变得可行，关键的瓶颈--特别是多项式乘法--必须是高效的。在本文中，我们给出了基于GPU的多项式乘法实现的一个特征。我们从模约简技术的概述开始，分析了广泛使用的Barrett模约简算法的几种变体。然后，我们提出了一种在图形处理器上针对位整数字进行优化的模约简变体，与现有的同类实现相比，获得了1.8$\x$的加速比。接下来，我们将探讨以下针对多项式乘法的特定于GPU的改进，旨在优化延迟和吞吐量：1)我们提出了一种NTT的2D混合基数、多块实现，与以前最先进的技术相比，它的平均加速比为1.85$\x$。2)我们探索了旨在减少冗余内存访问的共享内存优化，进一步将加速比提高了1.2$\x$。3)最后，我们将Hadamard乘积与NTT的相邻阶段进行了融合，将旋转因子的内存占用减少了50%。通过结合我们的ntt优化，我们获得了比以前最先进的ntt内核的中央处理器和图形处理器实现分别快123.13美元\倍$和2.37$\倍$的总体加速比。
Homomorphic Encryption (HE) enables users to securely outsource both the storage and computation of sensitive data to untrusted servers. Not only does HE offer an attractive solution for security in cloud systems, but lattice-based HE systems are also believed to be resistant to attacks by quantum computers. However, current HE implementations suffer from prohibitively high latency. For lattice-based HE to become viable for real-world systems, it is necessary for the key bottlenecks—particularly polynomial multiplication—to be highly efficient. In this paper, we present a characterization of GPU-based implementations of polynomial multiplication. We begin with a survey of modular reduction techniques and analyze several variants of the widely-used Barrett modular reduction algorithm. We then propose a modular reduction variant optimized for 64-bit integer words on the GPU, obtaining a 1.8$\times $speedup over the existing comparable implementations. Next, we explore the following GPU-specific improvements for polynomial multiplication targeted at optimizing latency and throughput: 1) We present a 2D mixed-radix, multi-block implementation of NTT that results in a 1.85$\times $average speedup over the previous state-of-the-art. 2) We explore shared memory optimizations aimed at reducing redundant memory accesses, further improving speedups by 1.2$\times$. 3) Finally, we fuse the Hadamard product with neighboring stages of the NTT, reducing the twiddle factor memory footprint by 50%. By combining our NTT optimizations, we achieve an overall speedup of 123.13$\times $and 2.37$\times $over the previous state-of-the-art CPU and GPU implementations of NTT kernels, respectively.