The CKKS Scheme

4b. The Two Types of Noise in CKKS

In CKKS, "noise" comes from two sources, unlike base LWE/RLWE schemes [2]:

1. Base Encryption Noise (\(e_1\))

Like standard LWE/RLWE encryption, CKKS ciphertexts include a small random noise \(e_1\) to ensure semantic security [2]:

\[\text{Enc}(\tilde{x}) = \big(a, \; b = (a \cdot s + \tilde{x} + e_1) \bmod q\big)\]

This noise grows as you perform additions and multiplications.

2. Encoding / Rounding Error (\(e_2\))

CKKS encodes real numbers as integers using a scale factor \(\Delta\) [4]:

\[ \tilde{x} = \text{Round}(x \cdot \Delta) \]

This means the encoded value can be seen as the "true" scaled value plus a small rounding error, \(e_2\):

\[ \tilde{x} = (x \cdot \Delta) + e_2 \]

Here, \(e_2\) is the rounding error. Unlike \(e_1\), it is not cryptographic; it represents the inherent approximation from scaling real numbers.

3. How Noise Propagates

• Addition: Noise adds linearly:
  \(c_1 + c_2 \implies e_\text{total} = e_1^{(1)} + e_1^{(2)} + e_2^{(1)} + e_2^{(2)}\)
• Multiplication: Noise grows roughly multiplicatively with the scale:
  Compact form:
  \(c_1 * c_2 \implies e_\text{total} \approx (\tilde{x} + e_1^{(1)} + e_2^{(1)}) (\tilde{y} + e_1^{(2)} + e_2^{(2)}) - \tilde{x}\tilde{y}\)
  Expanded form (main contributions):
  \(e_\text{total} \approx \tilde{x} e_1^{(2)} + \tilde{y} e_1^{(1)} + \tilde{x} e_2^{(2)} + \tilde{y} e_2^{(1)} + e_1^{(1)} e_1^{(2)} + \text{smaller cross-terms}\)
  Here, the terms involving \(\tilde{x}\) and \(\tilde{y}\) dominate the growth; the higher-order error products are typically much smaller.
• Rescaling: Divides both value and noise by Δ, keeping errors manageable for decoding.

4. Visualizing Noise

Think of CKKS ciphertexts as "fuzzy" numbers [4]:

✅ CKKS embraces the noise: the cryptographic noise e1 ensures security, while the encoding error e2 defines the unavoidable approximation. Controlled rescaling and scale management allow arithmetic on real numbers with predictable approximation.

5. Bounding Noise (The Noise Model)

CKKS papers and libraries don't use a single formula, but a noise model to track growth [4]. The primary goal is to ensure the final noise is smaller than the desired precision after decoding.

• Key Insight: Unlike other schemes where noise grows exponentially, CKKS's rescaling step makes the noise grow (at worst) linearly with the multiplicative depth.
• Parameter Selection: In practice, you tell the library your desired precision (e.g., 40 bits) and multiplicative depth (e.g., 7 levels). The library uses this noise model to automatically select parameters (like the polynomial degree \(N\) and the modulus chain \(q_L, ..., q_0\)) that guarantee the final error is acceptably small.
• Security: This bound is also crucial for security. To prevent "decryption attacks" (IND-CPA-D) where an attacker analyzes noise statistics, libraries add *new* random noise (called "noise flooding") after decryption to mask the original computation's noise.