Design of an Area-Effcient Million-Bit Integer Multiplier Using Double Modulus NTT

作者：Feng, Xiang; Li, Shuguo^*

来源：IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2017, 25(9): 2658-2662.

DOI：10.1109/TVLSI.2017.2691727

• Fully homomorphic encryption (FHE)
• large integer multiplication
• number theoretical transform (NTT)

This brief proposes a double modulus number theoretical transform (NTT) method for million-bit integer multiplication in fully homomorphic encryption. In our method, each NTT point is processed simultaneously under two moduli, and the final result is generated through the Chinese reminder theorem. The employment of double modulus enlarges the permitted NTT sample size from 24 to 32 bits and thus improves the transform efficiency. Based on the proposed double modulus method, we accomplish a VLSI design of million-bit integer multiplier with the Schonhage-Strassen algorithm. Implementation results on Altera Stratix-V FPGA show that this brief is able to compute a product of two 1024k-bit integers every 4.9 ms at the cost of only 7.9k ALUTs and 3.6k registers, which is more area-efficient when compared with the current competitors.

• 出版日期2017-9
• 单位清华大学