Efficient design-time flexible hardware architecture for accelerating homomorphic encryption

Official URL: https://dx.doi.org/10.1109/VLSI-SoC57769.2023.10321943

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 210 and 215. 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(n_2n) from O(n2). 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, 210 to 215