PaReNTT: Low-Latency Parallel Residue Number System and NTT-Based Long Polynomial Modular Multiplication for Homomorphic Encryption
PaReNTT: Low-Latency Parallel Residue Number System and NTT-Based Long Polynomial Modular Multiplication for Homomorphic Encryption
复制标题
DOI：
10.1109/tifs.2023.3338553
复制
发表时间：
2023-03
影响因子：
6.8
通讯作者：
Weihang Tan;S.W. Chiu;Antian Wang;Yingjie Lao;K. Parhi
中科院分区：
文献类型：
--
作者：
Weihang Tan;S.W. Chiu;Antian Wang;Yingjie Lao;K. Parhi
高速长多项式乘法在同态加密（HE）和格基密码系统中具有重要的应用。本文提出了一种基于数论变换（NTT）和逆NTT（iNTT）的长多项式模乘的低延迟硬件架构。提出了并行NTT和iNTT架构，以减少处理多项式的时钟周期数。利用中国剩余定理将模分解为多个更小的模。我们提出的架构，即PaReNTT，使三个新的贡献。首先，提出了级联并行NTT和iNTT架构，使得消除了在NTT的乘积输入到iNTT之前用于置换NTT的乘积的任何缓冲器要求。这是通过对NTT和iNTT使用不同的折叠组来实现的。其次，提出了一种新的方法来扩大一组可行的特殊模，其中模可以表示为几个有符号的2的幂项。第三，提出了用于使用CRT计算残差多项式的预处理和用于组合残差多项式的后处理的新架构。这些架构显著减少了预处理和后处理步骤的面积消耗。所提出的长模多项式乘法非常适合需要低延迟和高采样率的应用，例如在云中，因为这些前馈架构可以在任意级别进行流水线处理。流水线和延迟权衡也进行了研究。与现有设计相比，所提出的架构将延迟降低了49.2倍，并且查找表和DSP的面积-时间乘积（ATP）、ATP（LUT）和ATP（DSP）分别降低了89.2%和92.5%。具体来说，我们表明，对于$n=4096$和180位系数，建议的2并行架构需要6.3瓦的功率，同时在240 MHz，6模，每个长度30位，使用Xilinx Virtex Ultrascale+ FPGA。
High-speed long polynomial multiplication is important for applications in homomorphic encryption (HE) and lattice-based cryptosystems. This paper addresses low-latency hardware architectures for long polynomial modular multiplication using the number-theoretic transform (NTT) and inverse NTT (iNTT). Parallel NTT and iNTT architectures are proposed to reduce the number of clock cycles to process the polynomials. Chinese remainder theorem (CRT) is used to decompose the modulus into multiple smaller moduli. Our proposed architecture, namely PaReNTT, makes three novel contributions. First, cascaded parallel NTT and iNTT architectures are proposed such that any buffer requirement for permuting the product of the NTTs before it is input to the iNTT is eliminated. This is achieved by using different folding sets for the NTTs and iNTT. Second, a novel approach to expand the set of feasible special moduli is presented where the moduli can be expressed in terms of a few signed power-of-two terms. Third, novel architectures for pre-processing for computing residual polynomials using the CRT and post-processing for combining the residual polynomials are proposed. These architectures significantly reduce the area consumption of the pre-processing and post-processing steps. The proposed long modular polynomial multiplications are ideal for applications that require low latency and high sample rate such as in the cloud, as these feed-forward architectures can be pipelined at arbitrary levels. Pipelining and latency tradeoffs are also investigated. Compared to a prior design, the proposed architecture reduces latency by a factor of 49.2, and the area-time products (ATP) for the lookup table and DSP, ATP(LUT) and ATP(DSP), respectively, by 89.2% and 92.5%. Specifically, we show that for $n=4096$ and a 180-bit coefficient, the proposed 2-parallel architecture requires 6.3 Watts of power while operating at 240 MHz, with 6 moduli, each of length 30 bits, using Xilinx Virtex Ultrascale+ FPGA.