Paper 2025/777

Seamless Switching Between PBS and WoPBS for Scalable TFHE

Abstract

Fully Homomorphic Encryption (FHE) enables arbitrary computation directly on encrypted data. The TFHE scheme supports encryption of bits or small integers, evaluating any univariate function via programmable bootstrapping (PBS), which also refreshes ciphertext noise. Since both linear and nonlinear functions can be expressed with PBS, arbitrary circuits of unlimited depth can be computed without accuracy loss, aside from a negligible failure probability. However, a key limitation of TFHE is that it processes only single encrypted messages of small size; for larger messages, PBS becomes prohibitively expensive, as its cost grows rapidly with message bit-length. To address this, Without-Padding PBS (WoPBS) allows evaluation of larger lookup tables, and is practical up to 28 bits, offering significantly reduced latency compared to pure PBS. Recent advances in the WoPBS workflow have further optimized Circuit Bootstrapping (CBS) operations, narrowing the latency gap to PBS. Still, minimizing the underlying number of PBS operations remains crucial, as PBS dominates the cost. In this work, we introduce novel switching algorithms to efficiently convert ciphertexts between the PBS and WoPBS contexts, carefully managing noise growth while minimizing PBS invocations. This includes a modified batched Circuit Bootstrapping that converts an entire digit with a single Blind Rotation using our novel balanced and monomial selector bases, and a novel batched AES evaluation that halves the per-round Blind Rotations. We further integrate a state-of-the-art noise reduction method into the WoPBS workflow by adopting the centered mean noise reduction for both the PBSmanyLUT and the multi-bit Blind Rotation modulus switching, enabling more efficient parameter sets. All of our parameter sets meet the $\texttt{IND-CPA}^D$ failure budget of $2^{-128}$; under it, our workflows evaluate large lookup tables up to $1.9\times$ faster and AES-128 transciphering up to $1.6\times$ faster than the state of the art on the same machine, with our batched AES evaluation running $1.15\times$ faster than our binary workflow. Our CUDA implementation further evaluates one AES-128 block in 331\,ms on a single RTX 4090, $43\times$ faster than our single-threaded binary CPU workflow and $1.18\times$ faster than the recent Maverick GPU accelerator, whose parameters admit a failure probability of only about $2^{-40}$.