Leveled Fully Homomorphic Encryption

The defining characteristic of leveled FHE is that the multiplicative depth of the target computation must be known at key generation time. The scheme parameters are chosen to support exactly this depth and no more. This contrasts with pure FHE, which uses bootstrapping to handle unlimited depth. By eliminating bootstrapping, leveled schemes achieve significantly lower latency and higher throughput for fixed-depth computations like standard neural network inference.

Leveled FHE relies on modulus switching as its primary noise management technique. Each multiplication increases the inherent noise in the ciphertext. To compensate, the scheme uses a ladder of decreasing moduli. After a multiplication, the ciphertext is scaled down to a smaller modulus, which proportionally reduces the absolute noise. This process can only be repeated a finite number of times, defining the circuit's maximum depth before decryption becomes impossible.

Selecting parameters for a leveled scheme involves a direct trade-off between security level, circuit depth, and performance.

• Higher depth requires a larger initial modulus and larger polynomial ring dimensions, increasing ciphertext size and computation time.
• Higher security (e.g., 128-bit vs. 256-bit) also demands larger parameters.
• The art of leveled FHE is finding the minimal viable parameters for a specific task to minimize computational overhead.

Leveled FHE is the dominant approach for privacy-preserving machine learning inference. A standard neural network has a fixed, known architecture with a predictable number of sequential layers (multiplicative depth). The model owner can generate keys that exactly accommodate this depth. A client can then send an encrypted query, the server evaluates the model homomorphically, and returns an encrypted result—all without bootstrapping, making the process fast enough for near real-time applications.

The most common leveled FHE schemes are BGV (Brakerski-Gentry-Vaikuntanathan) and BFV (Brakerski-Fan-Vercauteren). Both operate over integer arithmetic and support SIMD-style batching.

• BGV manages noise via modulus switching, reducing the ciphertext modulus after each multiplication.
• BFV manages noise via scale-invariant techniques, keeping the modulus constant but allowing the noise to grow until a threshold. Both are excellent for exact computations on encrypted integers.

The term 'leveled' is often contrasted with 'pure' or 'fully bootstrappable' FHE.

• Leveled FHE: Parameters are set for a specific circuit depth L. After L multiplications, no further computation is possible. It is faster and simpler.
• Pure FHE: Uses bootstrapping to reset the noise, enabling unlimited depth. This adds significant computational overhead (often milliseconds per gate). In practice, most production FHE systems today are leveled, as bootstrapping remains too slow for many high-throughput applications.