TFHE Scheme

TFHE's defining feature is its ability to bootstrap after every single binary gate operation. Unlike leveled schemes that exhaust a noise budget, TFHE evaluates a boolean circuit gate-by-gate, refreshing the ciphertext noise immediately after each NAND or XOR. This enables unlimited circuit depth without pre-computing multiplicative depth. The bootstrapping procedure itself is the core computational unit, not a fallback recovery mechanism.

TFHE operates over the real torus (the continuous circle group R mod Z), representing plaintexts as points on a circle and ciphertexts as torus polynomials with added noise. This toroidal structure enables a natural mapping between continuous Gaussian error and discrete plaintext values. The scheme leverages TLWE (Torus Learning With Errors) samples, which generalize LWE over the torus, providing a unified framework for both encryption and bootstrapping operations.

TFHE excels at evaluating boolean circuits rather than arithmetic circuits. Each encrypted bit is an independent TLWE ciphertext, and operations proceed as logical gates. This makes TFHE ideal for:

• Decision trees and random forests
• Integer comparisons and sorting networks
• Lookup table evaluation
• Finite state machines The scheme is less suited for deep arithmetic circuits where packed SIMD schemes like CKKS dominate, but outperforms them on branching logic and bitwise operations.

A specialized bootstrapping variant that produces a low-noise ciphertext suitable for subsequent operations, rather than just a refreshed one. This enables composable function evaluation where the output of one bootstrapped gate feeds cleanly into the next. Circuit bootstrapping evaluates a lookup table while simultaneously reducing noise to a level compatible with linear operations like key switching, enabling deeper compositions of programmable bootstrapping blocks.

The core mathematical operation enabling TFHE bootstrapping is the external product between a TLWE ciphertext and a TRGSW (Torus Ring GSW) ciphertext. This operation multiplies an encrypted bit by an encrypted integer in the exponent, forming the basis for the accumulator update during bootstrapping. The external product is the computational bottleneck of TFHE, and its optimization through FFT-accelerated polynomial multiplication directly determines scheme performance.

The defining innovation of the TFHE scheme that goes beyond simple noise reduction. It evaluates a univariate lookup table (LUT) during the bootstrapping step, effectively computing an arbitrary function on the ciphertext. This enables the efficient evaluation of non-linear activation functions like ReLU or sigmoid directly on encrypted data, making TFHE uniquely suited for neural network inference.

A specialized TFHE operation that produces a low-noise ciphertext from a high-noise one while simultaneously evaluating a function. Unlike standard bootstrapping, the output is optimized for use in subsequent homomorphic operations. This composability is critical for evaluating deep circuits where the output of one bootstrapped gate must immediately feed into the next without a noise penalty.

TFHE operates on binary gates with fast bootstrapping after every operation, making it ideal for circuits with complex branching and non-linear functions. In contrast, the CKKS scheme excels at leveled arithmetic on packed real numbers using SIMD, but struggles with non-polynomial functions. TFHE is preferred for decision trees and neural network activations; CKKS dominates in linear algebra and statistical computation.

A design pattern that combines the strengths of TFHE and Multi-Party Computation (MPC). Linear operations are handled efficiently by HE, while complex non-linear functions are evaluated using fast MPC protocols. This hybrid approach optimizes end-to-end encrypted inference latency by avoiding the overhead of bootstrapping for every operation, delegating specific tasks to the most efficient cryptographic primitive.