Configurable Memory-Based NTT Architecture for Homomorphic Encryption

Abstract

Fully Homomorphic Encryption (FHE) is currently seen to be a promising solution for privacy-preserving applications. However, FHE suffers from a computational bottleneck due to the need to perform large polynomial calculations. Number Theoretic Transform (NTT) as a fundamental component of FHE is widely used to reduce latency and computation complexity while performing polynomial multiplication. Designing FHE can be challenging because it requires different settings depending on the application, such as the polynomial degree and coefficient modulus size. The hardware design has to stick to specific parameter values, which can make things harder to be implemented. In this brief, we present a configurable hardware accelerator for NTT that supports a wide range of parameter settings without any recompilation. This module is highly parallelized and designed for high throughput on the butterfly unit array. We provide a conflict-free access memory between the NTT Core and memory to increase performance. For the evaluation, our NTT and INTT modules show significant performance improvements compared to the CPU implementation using Microsoft’s SEAL 4.0 library by factors of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$8.88\times $ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$11.2\times $ </tex-math></inline-formula> , respectively. In comparison with the state-of-the-art hardware implementation, our module showed better performance with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$1.46\times $ </tex-math></inline-formula> improvement of throughput/slice metric as a fair comparison while consuming fewer hardware resources.

Topics & Concepts