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

Abstract

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 Cooley-Turkey DIT NTT algorithm and Gentleman-Sande DIF NTT Algorithm.

Existing System

Grammar-School Multiplication Method, Karatsuba–Ofman Method, Toom–Cook Method.

Proposed System

In this paper, we proposed a double modulus NTT method to enlarge the digit size of NTT and introduced a DIF-DIT hybrid NTT approach to eliminate the reorder operations. Based on the proposed method and introduced approach, we accomplished a VLSI design of an area-efficient pipeline million-bit multiplier. Synthesis result on FPGA showed that our multiplier was more area efficient compared with the previous works, which made our design practical for area constraint FHE applications.

Architecture

BLOCK DIAGRAM