Leveled Fully Homomorphic Encryption

The defining characteristic of leveled FHE is that the multiplicative depth of the target computation must be known before encryption. The scheme parameters—specifically the modulus chain—are calibrated to support exactly this depth. If the actual computation exceeds this bound, the noise budget is exhausted, and decryption fails. This requires developers to analyze their model architecture statically, flattening conditional branches into fixed-depth arithmetic circuits. For neural networks, this means the number of sequential encrypted layers is fixed at compilation time.

Unlike pure FHE schemes, leveled FHE eliminates bootstrapping entirely. Bootstrapping is the computationally dominant operation in schemes like TFHE, often consuming over 95% of total runtime. By forgoing this step, leveled schemes achieve orders of magnitude lower latency per operation. The trade-off is finite computation depth. This makes leveled FHE ideal for encrypted inference where the model graph is a fixed directed acyclic graph (DAG) with a known number of sequential multiplications.

Leveled FHE schemes like CKKS and BGV operate over a chain of decreasing moduli. Each multiplication consumes one modulus level through rescaling or modulus switching. The initial ciphertext modulus is chosen to be large enough to accommodate the total number of these operations. As computation proceeds down the chain, the ciphertext shrinks, and the effective precision decreases. This is analogous to managing a fixed-precision budget that is consumed deterministically with each operation.

Leveled schemes heavily leverage ciphertext packing to encode thousands of plaintext values into a single ciphertext. This enables Single Instruction Multiple Data (SIMD) parallelism, where one homomorphic addition or multiplication simultaneously processes all packed slots. For machine learning, this maps naturally to batched inference or neuron-level parallelism within a layer. The amortized cost per operation drops proportionally to the packing density, making leveled FHE throughput competitive for high-volume encrypted inference serving.

Leveled FHE natively supports only addition and multiplication. Non-linear activation functions like ReLU, sigmoid, or max-pooling must be replaced with low-degree polynomial approximations. The degree of the approximation directly consumes multiplicative depth. This creates a design tension: higher-degree polynomials yield better accuracy but consume more levels, potentially exceeding the circuit budget. Common techniques include using Chebyshev or minimax approximations to minimize depth while maintaining acceptable inference accuracy.

Each homomorphic multiplication increases the ciphertext size from two ring elements to three. Without intervention, subsequent multiplications would cause exponential growth. Relinearization is a key-switching procedure that reduces the ciphertext back to two elements, enabling chained multiplications. This operation requires relinearization keys to be generated during setup and consumes one level of the modulus chain. In leveled FHE, relinearization is applied after every multiplication to maintain compact ciphertexts.