Paper 2026/810

Accelerating TFHE: Scalable Multiplication Algorithms and Efficient Carry Handling

Abstract

Fully Homomorphic Encryption (FHE) enables private data processing on untrusted servers. However, FHE performance remains a critical bottleneck for applications such as machine learning, which rely heavily on non-linear operations, such as comparisons, and numerous ciphertext-ciphertext (CxC) and ciphertext-plaintext (CxP) multiplications. While modern FHE schemes such as TFHE efficiently handle non-linear operations, multiplication remains a significant performance bottleneck. This paper introduces new algorithms for CxC and CxP multiplication, as well as a ciphertext-plaintext dot-product algorithm, a critical kernel in machine-learning inference and convolution. Our approach uses Circuit Bootstrapping and Vertical Packing to generate partial products for CxC and CxP multiplication. The dot-product algorithm instead accumulates contributions from many multiplications directly, avoiding the cost of computing and adding each product separately. All three algorithms organize terms by output bit position, reduce them in parallel using carry-save compression or bound-driven reduction trees, and defer carry propagation to an efficient CMux-based final stage. We evaluate our algorithms and their parallel implementations against the default implementation in TFHE-rs and recent state-of-the-art approaches. Our results demonstrate speedups of up to $31.65\times$ on CPUs and $31.22\times$ on GPUs relative to TFHE-rs, and accelerate real-world neural network layers by up to $4.81\times$ over the fastest prior methods.