TFHE Scheme

Unlike leveled schemes that require pre-determined circuit depths, TFHE performs bootstrapping after every binary gate evaluation. This refreshes the noise budget immediately, enabling unbounded computation depth without prior knowledge of the circuit. Each NAND gate operation triggers a blind rotation that simultaneously resets noise and evaluates the gate function, making TFHE ideal for complex, branching programs where the computation path is not known in advance.

TFHE's defining innovation extends bootstrapping beyond noise management. Programmable bootstrapping evaluates a lookup table (LUT) during the noise refresh, mapping an encrypted input to an arbitrary encrypted output in a single operation.

• Evaluates any univariate function on encrypted data
• Replaces polynomial approximations with exact LUT evaluations
• Enables non-linear activations like ReLU or sigmoid directly on ciphertexts
• Serves as the foundation for encrypted neural network inference

The cryptographic engine of TFHE is the blind rotation, which homomorphically shifts a polynomial ring element by an encrypted value. This operation effectively performs a circular shift on an encrypted vector, enabling the extraction of specific coefficients that encode the result of a lookup table evaluation. The blind rotation leverages RLWE-based key switching and Gadget decomposition to achieve sub-second bootstrapping latencies, making TFHE the fastest FHE scheme for evaluating individual gates.

TFHE natively operates on encrypted bits rather than encrypted integers, evaluating circuits gate by gate. This contrasts with schemes like CKKS and BFV that perform word-level arithmetic via SIMD packing.

• TFHE: Optimal for boolean circuits, comparisons, and bitwise operations
• CKKS/BFV: Optimal for vectorized arithmetic on large datasets
• Trade-off: TFHE excels at low-latency, single-bit operations; word-level schemes offer higher throughput for batched computations
• Hybrid approaches now combine TFHE bootstrapping with CKKS arithmetic for optimal performance across diverse workloads

TFHE achieves bootstrapping in under 13 milliseconds on modern hardware, a dramatic improvement over earlier schemes that required seconds or minutes. This speed enables practical interactive applications:

• Encrypted real-time control systems
• Privacy-preserving biometric authentication
• Secure database queries with response times acceptable for user-facing applications

The scheme's computational efficiency stems from its use of torus-based arithmetic and optimized FFT-based polynomial multiplications.

TFHE represents ciphertexts as elements on the real torus (the continuous circle group), enabling efficient discretization and noise management. This mathematical structure allows:

• Exact representation of binary values as torus phases
• Natural compatibility with floating-point-like operations
• Efficient blind rotations via polynomial ring structures over the torus

The torus formulation bridges the gap between continuous real-number arithmetic and discrete lattice-based cryptography, providing a clean algebraic framework for gate-level homomorphic evaluation.