Circuit Bootstrapping

The core mechanism that distinguishes circuit bootstrapping from standard noise reduction. It homomorphically evaluates a Look-Up Table (LUT) encoded in the bootstrapping key. This transforms an encrypted input message into an encrypted output message according to an arbitrary univariate function f(x), while simultaneously resetting the noise budget to a fixed low level. This enables the evaluation of non-linear activation functions directly on encrypted data.

Unlike leveled FHE where operations consume a finite noise budget, circuit bootstrapping produces a refreshed ciphertext with a guaranteed noise level. This output can immediately serve as input for another bootstrapping operation. This property enables the construction of arbitrarily deep circuits without the noise accumulation that causes decryption failure, making it essential for complex encrypted control flow and iterative algorithms.

The bootstrapping procedure evaluates a univariate function encoded as a look-up table. This allows the direct homomorphic evaluation of functions that are difficult to approximate with polynomials, such as:

• Sign function and step functions
• ReLU and other activation functions
• Rounding and quantization operations
• Arbitrary boolean gates (AND, OR, XOR) on encrypted bits

A throughput optimization technique that encodes multiple independent LUT evaluations into a single bootstrapping operation. By packing several plaintext values into the slots of a single RLWE ciphertext and applying a multi-output LUT, circuit bootstrapping can evaluate the same function on multiple encrypted inputs simultaneously. This dramatically improves the amortized cost per operation in batched inference scenarios.

Gate bootstrapping (TFHE's foundational operation) evaluates a single binary gate and produces a ciphertext suitable only for further gate operations. Circuit bootstrapping extends this by producing a ciphertext with a low-noise encoding compatible with leveled operations (additions, multiplications) before the next bootstrap. This bridges the gap between fast boolean circuits and arithmetic operations, enabling mixed-circuit evaluation.

The computational cost of circuit bootstrapping is dominated by the external product between an RLWE ciphertext and a precomputed Bootstrapping Key (BSK). The BSK encrypts the secret key under itself in a GSW-like format. Optimizing this external product—through hardware acceleration or algorithmic improvements like multi-bit PBS—is the primary focus for reducing latency in production FHE deployments.

The finite capacity for error accumulation within a ciphertext. Every homomorphic operation, especially multiplication, consumes this budget. Circuit bootstrapping is the mechanism that resets this budget.

• Analogy: Think of it as a signal-to-noise ratio that degrades with each operation.
• Exhaustion: Once the noise overwhelms the message, decryption returns garbage.
• Reset Mechanism: Circuit bootstrapping homomorphically evaluates the decryption circuit to produce a fresh ciphertext with a full noise budget, enabling unlimited computation depth.

Techniques that encode multiple plaintext values into a single ciphertext to enable Single Instruction Multiple Data (SIMD) parallelism. Circuit bootstrapping interacts with packing by allowing operations on individual slots.

• Throughput: Packing thousands of values into one ciphertext dramatically improves amortized performance.
• Slot Manipulation: Circuit bootstrapping can be used to extract or manipulate specific slots without decrypting the entire packed vector.
• Trade-off: Packing is standard in schemes like CKKS, but TFHE's circuit bootstrapping enables bit-precise operations on packed data.

A cryptographic operation that transforms a ciphertext encrypted under one secret key into a ciphertext encrypting the same message under a different key. It is a fundamental building block used inside circuit bootstrapping.

• Relinearization: A specific key-switch that reduces ciphertext size after multiplication.
• Bootstrapping Role: The bootstrapping procedure internally uses key-switching to convert between the encryption keys used for the blind rotation and the final output.
• Security: Requires public evaluation keys (key-switching keys) that do not reveal the underlying secret keys.

A critical distinction in TFHE literature. Functional bootstrapping (or programmable bootstrapping) outputs a ciphertext encrypting f(m) with reduced noise, while circuit bootstrapping outputs a ciphertext encrypting the same message m but with a specific, low-noise format suitable for subsequent operations.

• Output Format: Circuit bootstrapping specifically produces a ciphertext with minimal noise variance, often converting from a TLWE to a TRLWE or TRGSW sample.
• Composability Goal: The primary goal is to enable the output to be used directly in further leveled operations without immediate re-bootstrapping.