An Area-Efficient Large Integer NTT-Multiplier Using Discrete Twiddle Factor Approach

作者：Li, Zhenmin; Ren, Jingwei; Du, Gaoming^*; Tu, Zhenxing; Wang, Xiaolei; Yin, Yongsheng; Ouyang, Yiming

来源：IEEE Transactions on Circuits and Systems II: Express Briefs , 2023, 70(2): 751-755.

DOI：10.1109/TCSII.2022.3215903

• Transforms
• Galois fields
• Delays
• Data compression
• Memory management
• Indexes
• Field programmable gate arrays
• Large number multiplier
• twiddle factor
• number theoretic transform
• FPGA

Number theoretic transform (NTT) method shows great advantages in speed and efficiency for applications such as homomorphic encryption. However, the twiddle factor data consumes a lot of memories. In this brief, we propose a novel data compression method, together with the corresponding data storage scheme and addressing algorithm. Furthermore, we design a 768k-bit multiplier with a full pipeline structure. Our proposed compression method has achieved a compression rate of 98.8% for the twiddle factor data. Compared with the state-of-the-art FPGA implementations, our design shows up to 44.2% improvement in terms of area-efficiency.