BatchBoot: Fast Batched Bootstrapping for TFHE scheme and Practical Applications

Torus-based Fully Homomorphic Encryption (TFHE) is distinguished by its unique bootstrapping mechanism, which enables arbitrary computation while refreshing the noise budget. However, this mechanism exhibits limited scalability since it can handle only a single encrypted message at a time. To address this, recent studies have proposed batched bootstrapping schemes that allow TFHE to process ciphertexts in parallel, thereby achieving promising amortization benefits. Despite these advances, this emerging direction remains underexplored, leaving ample room for further investigation.

In this paper, we present BatchBoot, an efficient batched bootstrapping framework for TFHE that enables amortized processing of encrypted messages. Specifically, our work makes three key contributions. First, we redesign the core submodule, i.e., homomorphic polynomial multiplication, to substantially reduce the reliance on expensive FFT operations. Second, we propose a sparsity-aware message packing strategy that flexibly supports varying packing scales. Third, we extend functional bootstrapping to circuit bootstrapping, thereby greatly enhancing the expressiveness of supported functions. Together, these contributions enable BatchBoot to deliver a 2.4× speedup over the state-of-the-art batched scheme (Guimarães et al., CCS'25) and a 43.8× improvement over the non-batched TFHE-rs implementation.

At the application level, we highlight the versatility of BatchBoot through two practical use cases. First, we present the first TFHE-based PSI protocol under the unbalanced setting, which achieves a 294× reduction in communication cost and a 4.1× speedup compared to the best BFV-based solution (PEPSI, USENIX Security'24). Second, we design an 8-bit FHE instruction set based on the BatchCBoot that delivers up to a 5.4× speedup over the existing results (Wang et al., CCS'25).