Noise Budget

Every Ring Learning With Errors (RLWE) ciphertext contains a limited amount of inherent noise. Each homomorphic operation—especially multiplication—consumes a portion of this budget. Once the noise overwhelms the plaintext signal relative to the ciphertext modulus, the decryption algorithm can no longer recover the original message, resulting in a corrupted output. This imposes a strict upper bound on multiplicative depth.

Noise accumulation is not linear. Addition adds noise roughly additively, consuming a small, predictable amount of the budget. Multiplication, however, causes the noise to grow multiplicatively, roughly squaring the noise magnitude. This rapid growth is the primary constraint in leveled fully homomorphic encryption schemes, forcing developers to structure circuits with minimal multiplicative depth.

Several cryptographic techniques actively manage the noise budget:

• Modulus Switching: Scales down the ciphertext modulus to proportionally reduce absolute noise, effectively resetting the relative noise ratio without decryption.
• Rescaling (CKKS): Divides the ciphertext by a scale factor after multiplication, maintaining a stable scale and controlling noise growth.
• Bootstrapping: Homomorphically evaluates the decryption circuit to produce a fresh ciphertext with a full noise budget, enabling unbounded computation depth.

Bootstrapping is the only mechanism to achieve fully homomorphic encryption (FHE) rather than merely leveled HE. By encrypting the secret key under itself and evaluating the decryption circuit homomorphically, bootstrapping strips away accumulated noise and outputs a new ciphertext with a refreshed budget. This operation is computationally expensive but essential for programs with unknown or unbounded depth.

Before executing a computation, developers must estimate the multiplicative depth of the arithmetic circuit. In the CKKS scheme, parameters like the coefficient modulus chain are chosen based on this depth. If the estimated depth exceeds the available budget, the computation must be restructured—by minimizing multiplications, using polynomial approximations for non-linear functions, or inserting bootstrapping operations.

A larger ciphertext modulus provides a larger initial noise budget but weakens the underlying lattice-based security assumption. To maintain a target security level (e.g., 128-bit), parameter sizes must increase, leading to larger ciphertexts and slower operations. This creates a trilemma between computational depth, security margin, and performance, requiring careful parameter selection for each use case.

The accumulation of error inherent in lattice-based ciphertexts with each homomorphic operation. Noise grows additively with addition but multiplicatively with multiplication, making multiplication the primary consumer of the noise budget.

• Addition: Noise grows as E₁ + E₂ (linear, manageable)
• Multiplication: Noise grows as E₁·E₂ + E₁·m₂ + E₂·m₁ (quadratic, dominant)
• Depth tracking: Circuit designers must model noise growth to ensure decryption remains correct

A noise management technique that scales down a ciphertext to a smaller modulus, proportionally reducing the absolute noise magnitude. This operation is performed without knowledge of the secret key and is essential in leveled FHE schemes.

• Mechanism: Divides both ciphertext and modulus by a scaling factor
• Effect: Reduces noise by approximately the same factor
• Trade-off: Each switch consumes one level from the modulus chain, limiting remaining multiplicative depth

In the CKKS scheme, the operation that divides a ciphertext by a scale factor after multiplication to maintain a stable scale and manage noise growth. Analogous to truncating floating-point precision in the encrypted domain.

• Purpose: Prevents exponential growth of the scale factor during multiplication
• Noise benefit: Simultaneously reduces noise proportionally to the scaling factor
• Level consumption: Each rescaling reduces the available modulus chain by one level

A key-switching procedure that reduces ciphertext size after multiplication from three ring elements back to two. Without relinearization, each multiplication would increase ciphertext dimension quadratically, rapidly consuming the noise budget.

• Required keys: Relinearization keys (public evaluation keys)
• When to apply: Immediately after every ciphertext multiplication
• Noise impact: Introduces a small additive noise term from the key-switching operation itself

An extension of TFHE bootstrapping that simultaneously refreshes ciphertext noise and evaluates a univariate lookup table function. This enables efficient evaluation of non-linear operations like activation functions while resetting the noise budget.

• Dual purpose: Noise refresh + function evaluation in one operation
• Use case: Applying ReLU or sigmoid during encrypted neural network inference
• Efficiency: Avoids separate bootstrapping and polynomial approximation steps