VLSI Design of Programmable Bootstrapping for Torus Fully Homomorphic Encryption

Torus-based fully homomorphic encryption (TFHE) is notable for its faster and programmable bootstrapping (PBS) algorithm. However, TFHE suffers from its high computational complexity in PBS, especially in the blind rotation (BR) process. BR involves multiple iterations of vector-matrix multiplication of polynomials, necessitating the use of Number Theoretic Transform (NTT) for efficient computation. Moreover, algorithm optimization, such as bootstrapping key unrolling, requires more expensive computations of an iteration in BR, leading to an increased number of NTT. This work mainly explores the design of reduced NTT (RNTT), which leverages the sparsity of polynomial multiplications in PBS. We proposed a reconfigurable RNTT architecture with an efficient memory conflict-free addressing algorithm adaptable to different configurations. Experimental results show that the developed RNTT design only requires less than 2% area and latency compared to a highly parallel approach. A low-complexity PBS design is then developed. The result achieves 1.8X higher throughput per area compared to the related work.