Noise Growth

Homomorphic operations impact the noise budget asymmetrically. Addition introduces a small, linear increase in noise, typically negligible for circuit depth planning. Multiplication, however, causes the internal noise terms to multiply together, resulting in quadratic noise growth. This disparity means that the multiplicative depth of a circuit—the longest chain of sequential multiplications—is the primary determinant of whether a ciphertext will decrypt correctly. Managing this requires careful circuit design, minimizing multiplication depth where possible.

Every ciphertext is initialized with a finite noise budget, determined by the encryption parameters (modulus size and error distribution). This budget represents the maximum error the ciphertext can accumulate before the plaintext message is corrupted beyond recovery. Key aspects include:

• Initial Budget: Set during encryption; larger moduli provide deeper computation capacity but increase ciphertext size.
• Budget Consumption: Each multiplication consumes a significant fraction of the remaining budget.
• Decryption Failure: Occurs when the accumulated noise exceeds the threshold, causing the plaintext to be lost in the statistical error.

To prevent decryption failure, modern FHE schemes employ active noise management:

• Bootstrapping: Homomorphically evaluates the decryption circuit on a noisy ciphertext, producing a new ciphertext encrypting the same message with a refreshed noise budget. This enables unlimited computation depth but is computationally expensive.
• Modulus Switching: Scales down the ciphertext modulus, which proportionally reduces the absolute noise magnitude without decryption. This is a lightweight, leveled technique used in schemes like BGV and BFV.
• Rescaling (CKKS): After a multiplication, the ciphertext is divided by a scale factor to maintain a stable scale and truncate noise, analogous to managing floating-point precision.

Noise growth directly constrains the architecture of models used for encrypted inference. Deep neural networks with many sequential layers (high multiplicative depth) are challenging to evaluate directly. Mitigation strategies include:

• Polynomial Approximation: Replacing non-linear activation functions (ReLU, sigmoid) with low-degree polynomial approximations to reduce multiplicative depth.
• Circuit Bootstrapping: Using programmable bootstrapping in TFHE to evaluate non-linear functions as lookup tables while simultaneously refreshing noise.
• Hybrid Protocols: Offloading non-linear operations to a Multi-Party Computation (MPC) protocol, which does not suffer from noise growth, while using HE for linear layers.

Beyond noise magnitude, multiplication causes the ciphertext dimension to grow. In RLWE-based schemes, multiplying two ciphertexts of dimension 2 produces a ciphertext of dimension 3. Without correction, subsequent multiplications would cause exponential dimension growth, making storage and computation impractical. Relinearization is a key-switching operation that reduces the product ciphertext back to dimension 2, enabling a chain of multiplications without dimensional explosion. This requires specific evaluation keys (relinearization keys) to be generated by the secret key holder.

Selecting encryption parameters is a direct negotiation with noise growth. Larger parameters increase the initial noise budget and computational capacity but degrade performance:

• Polynomial Modulus Degree (N): Higher N increases security and budget but slows operations.
• Coefficient Modulus (Q): A larger Q provides a deeper budget but must be carefully chosen to avoid security vulnerabilities.
• Error Distribution: A smaller standard deviation reduces initial noise but can weaken security if too aggressive. The goal is to select the minimal parameters that satisfy both the security level (e.g., 128-bit) and the circuit's multiplicative depth requirement.