Efficient Design-Time Flexible Hardware Architecture for Accelerating Homomorphic Encryption

This paper presents a design-time configurable hardware generator for hardware acceleration of the CKKS Fully Homomorphic Encryption (FHE) scheme. Our design aims to accelerate the multiplication and relinearization operations of the CKKS. It includes a design-time configurable Number Theoretic Transform (NTT) multiplication hardware for polynomial sizes between 2(10) and 2(15). The NTT-based multiplication realizes modular multiplication using an efficient word-level Montgomery reduction algorithm.

Polynomial multiplication is a bottleneck for the FHE operations. The NTT enables very fast polynomial multiplication by reducing its complexity to O(nlog(2)n) from O(n(2)). The fundamental arithmetic block of the NTT operation is the butterfly, which implements four different operations, namely, modular multiplication and modular addition/subtraction.

The memory access pattern (MAP) of the NTT operation is complex, and it is crucial to design an efficient MAP for NTT for implementing a high-throughput NTT architecture. We designed and implemented an efficient algorithm for the MAP of NTT and generalized this approach for polynomial sizes, 2(10) to 2(15).