A Bootstrapping-Capable Configurable NTT Architecture for Fully Homomorphic Encryption

Abstract

Fully homomorphic encryption (FHE) provides a solution to privacy-preserving applications because of its ability to perform computations on encrypted data without exposing raw data. However, FHE suffers from implementation bottlenecks owing to the large computations involved, particularly with bootstrapping. Bootstrapping is necessary in FHE to enable an unlimited number of multiplication. Nonetheless, implementing bootstrapping requires a significantly large polynomial length, $N=2^{16}$ or 217, to considerably secure the system. Thus, polynomial multiplication will be challenging in terms of resources and time. This problem can be resolved by implementing the number theoretic transform (NTT) that can perform polynomial multiplication in quasi-linear complexity. However, designing an NTT architecture for FHE is challenging because it requires various parameters, particularly the high polynomial degree that will require a considerable amount of hardware resources and clock latency. This study proposes a design for FPGA implementation of the NTT architecture with flexible input lengths: 216 and 217 by combining radix-2 and radix-24. Twiddle factor generator (TFG) and efficient configurable modular multiplication (MM) unit are also utilized to achieve time and area-efficient architecture. The proposed design was synthesized on the FPGA Xilinx ALVEO U250 and demonstrated higher hardware efficiency and optimum latency that outperforms those reported in previous studies.

Keywords

• Homomorphic encryption
• configurable architecture
• lattice-based cryptography
• number theoretic transform