Paper 2025/2150

Low-Latency Fully Homomorphic Arithmetic Using Parallel Prefix Group Circuit with Primitive Gate Bootstrapping

Abstract

Fully Homomorphic Encryption over the Torus (TFHE) is a fully homomorphic encryption scheme that efficiently supports Boolean logic gates by performing gate operations and refreshing ciphertext noise with single gate bootstrapping. However, its operation is limited to simple two-input gates such as AND, OR, XOR and NAND, requiring deep circuits and multiple bootstrapping steps to support more complex arithmetic. In this paper, we propose Primitive Gate Bootstrapping, a new algebraic framework that significantly expands the class of Boolean functions evaluable with a single bootstrapping. By formalizing bootstrappable functions as compositions of linear maps and negacyclic functions, called the Blind-Rotational Function Family (BRFF), we define a subclass, the Primitive Gate Family (PGF). This family includes multi-input hybrid gates such as l-input XOR, 3-input Majority, and AND-XOR, which can all be realized with a single bootstrapping. Building on PGF, we further design a general circuit framework called the Parallel Prefix Group Circuit (PPGC) for efficiently implementing arithmetic and logical operations. PPGC enable n-bit addition, subtraction, comparison, equality, select, minimum/maximum, absolute, and negation with logarithmic depth O(log n) and significantly reduced latency compared to TFHE. In particular, our optimized implementations of addition and subtraction achieve a 1.92× speedup over TFHE, while the size of the blind rotation key was reduced by approximately 40%. In addition to the two-input addition, we also introduce an efficient technique for multi-input addition, which is particularly useful in applications such as encrypted matrix multiplication. Therefore, it is clear that the PGF-based constructions offer a practically scalable and efficient foundation for depth-sensitive homomorphic computations