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

摘要

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.

关键词