exhaust-noise-budget.ipynb

Kernel: SageMath 10.0

Break: Exhausting the FHE Noise Budget

Module 11 | Breaking Weak Parameters

Chain enough homomorphic multiplications to push noise past the decryption threshold and watch ciphertexts decay into garbage.

Why This Matters

FHE ciphertexts carry noise that grows with every homomorphic operation. Addition grows noise linearly ($e_1 + e_2$), but multiplication grows it multiplicatively ($\sim e_1 \cdot e_2$). Once noise exceeds a threshold determined by the modulus $q$, decryption produces garbage.

This means every FHE scheme has a noise budget: a maximum number of operations (especially multiplications) before the ciphertext becomes useless. Understanding noise budgets is essential for:

• Choosing parameters ($n$, $q$, $t$) that support enough computation depth

• Deciding when bootstrapping is needed

• Understanding why FHE is so much slower than plaintext computation

In this notebook, we'll deliberately exhaust the noise budget and observe the transition from correct decryption to complete failure.

The Scenario

We use the toy symmetric LWE-like scheme from Notebook 11a. The scheme encrypts a message $m$ into the plaintext space $\mathbb{Z}_t$ (integers mod $t$) using a ciphertext space $\mathbb{Z}_q$ (integers mod $q$):

• Secret key: $s \in \mathbb{Z}_q$

• Encrypt $m$: pick random $a \in \mathbb{Z}_q$, small noise $e$; output $(a,\; b = a \cdot s + \Delta \cdot m + e \pmod{q})$ where $\Delta = \lfloor q/t \rfloor$

• Decrypt $(a, b)$: compute $v = b - a \cdot s \pmod{q}$, then $m = \lfloor t \cdot v / q \rceil \bmod t$

The scaling factor $\Delta = \lfloor q/t \rfloor$ separates the message from the noise. Decryption succeeds as long as the noise $|e| < \Delta / 2$.

# === BFV-like toy scheme parameters ===
q = 32768       # ciphertext modulus (2^15)
t = 16          # plaintext modulus (small for clarity)
Delta = q // t  # scaling factor = 2048
B = 3           # initial noise bound

print(f'Parameters:')
print(f'  Ciphertext modulus q = {q}')
print(f'  Plaintext modulus  t = {t}')
print(f'  Scaling factor Delta = floor(q/t) = {Delta}')
print(f'  Noise bound B = {B}')
print(f'  Max tolerable noise: Delta/2 = {Delta // 2}')
print()
print(f'Decryption works when |noise| < {Delta // 2}.')
print(f'Initial noise is at most {B}, so we have room for growth.')

def centered_mod(x, q):
    """Reduce x mod q into [-q/2, q/2)."""
    r = x % q
    if r > q // 2:
        r -= q
    return r

def keygen():
    """Generate a random secret key."""
    return randint(1, q - 1)

def encrypt(m, s):
    """Encrypt message m in Z_t. Returns (a, b, noise)."""
    a = randint(0, q - 1)
    e = randint(-B, B)
    b = (a * s + Delta * (m % t) + e) % q
    return (a, b, e)  # return noise for tracking

def decrypt(ct, s):
    """Decrypt ciphertext (a, b). Returns (message, raw_noise)."""
    a, b = ct[0], ct[1]
    v = centered_mod(b - a * s, q)
    # Round to nearest multiple of Delta, then divide
    m = round(t * v / q) % t
    # Compute actual noise for diagnostics
    noise = centered_mod(v - Delta * m, q)
    return m, noise

# Test basic encrypt/decrypt
s = keygen()
m_test = 7
ct_test = encrypt(m_test, s)
dec_test, noise_test = decrypt(ct_test, s)

print(f'Secret key: s = {s}')
print(f'Encrypt m = {m_test}')
print(f'Ciphertext: (a={ct_test[0]}, b={ct_test[1]})')
print(f'Noise injected: e = {ct_test[2]}')
print(f'Decrypted: {dec_test}  (noise recovered: {noise_test})')
print(f'Correct? {dec_test == m_test}')

Step 1: Encrypt and Measure Initial Noise

Let's encrypt a value and measure the noise. The noise is the difference between the "ideal" ciphertext value $\Delta \cdot m$ and the actual value recovered during decryption. As long as $|\text{noise}| < \Delta / 2 = 1024$, we can round correctly.

# Encrypt a value and track noise
m = 5
ct = encrypt(m, s)
dec, noise = decrypt(ct, s)

print(f'Message: m = {m}')
print(f'Delta * m = {Delta * m}')
print(f'Injected noise: {ct[2]}')
print(f'Measured noise after decrypt: {noise}')
print(f'Noise budget remaining: {Delta // 2 - abs(noise)} out of {Delta // 2}')
print(f'Decrypted correctly: {dec == m}')
print()
print(f'Noise is tiny ({abs(noise)}) vs threshold ({Delta // 2}).')
print(f'We have LOTS of room. Let us burn through it with multiplications.')

Step 2: Simulate Homomorphic Multiplication and Noise Growth

In a BFV/BGV-like scheme, multiplying two ciphertexts with noise $e_1$ and $e_2$ produces a result with noise roughly proportional to $e_1 \cdot e_2 \cdot t$. We simulate this noise growth model:

$$e_{\text{product}} \approx e_1 \cdot e_2 \cdot t / \Delta + e_1 + e_2$$

For simplicity, we use the conservative bound: $|e_{\text{new}}| \approx |e_{\text{old}}| \cdot |e_{\text{fresh}}| \cdot t / \Delta + |e_{\text{old}}| + |e_{\text{fresh}}|$.

We'll chain multiplications: start with $\text{Enc}(m)$, then multiply by $\text{Enc}(2)$ repeatedly, computing $m \cdot 2^k \bmod t$.

# Simulate noise growth from chained multiplications
# We model noise growth: after multiplying two ciphertexts with noise e1, e2,
# the resulting noise is approximately e1 * e2 * (t / Delta) + e1 + e2

initial_noise = B  # worst-case initial noise
threshold = Delta // 2  # decryption fails above this

noise = initial_noise
fresh_noise = initial_noise  # each new ciphertext has noise ~ B

# Also track the plaintext to verify correctness
m_val = 3  # start with m = 3
mul_factor = 2  # multiply by 2 each time


results = [(0, m_val, noise, 'OK')]

for k in range(1, 20):
    # Noise growth model for multiplication
    noise_new = abs(noise * fresh_noise * t) // Delta + abs(noise) + abs(fresh_noise)
    noise = noise_new
    m_val = (m_val * mul_factor) % t
    
    if noise < threshold:
        status = 'OK'
    else:
        status = 'FAILED'
    
    results.append((k, m_val, noise, status))
    pct = min(100 * noise / threshold, 9999)
    
    if noise > threshold * 100:
        print(f'  ... noise has exploded, stopping.')
        break

Step 3: Visualize the Noise Explosion

Let's plot the noise level versus the number of multiplications. The exponential growth is dramatic: a few multiplications are fine, but the noise quickly crosses the decryption threshold.

# Plot noise growth vs multiplication count
mults = [r[0] for r in results]
noises = [r[2] for r in results]

p1 = list_plot(
    list(zip(mults, noises)),
    plotjoined=True,
    color='red',
    thickness=2,
    marker='o',
    legend_label='Noise level'
)

# Add the threshold line
p2 = line(
    [(0, threshold), (max(mults), threshold)],
    color='blue',
    linestyle='--',
    thickness=2,
    legend_label=f'Threshold (Delta/2 = {threshold})'
)

show(
    p1 + p2,
    title='Noise Growth from Chained Multiplications',
    axes_labels=['Number of multiplications', 'Noise level'],
    scale='semilogy',
    figsize=(8, 5)
)

# Find the failure point
failure_point = None
for r in results:
    if r[3] == 'FAILED':
        failure_point = r[0]
        break

if failure_point:
    print(f'Decryption fails after {failure_point} multiplications.')
    print(f'This is the "multiplicative depth" of this parameter set.')
else:
    print('Decryption survived all multiplications (unlikely with these parameters).')

Step 4: Observe Decryption Failure

Let's actually perform a concrete multiplication chain in our toy scheme and watch the decrypted value go from correct to garbage. We'll simulate the noisy ciphertext values directly.

# Concrete demonstration: encrypt, multiply, decrypt at each step
# We simulate the ciphertext as (encoded_message + noise) mod q
# and multiply by applying the noise growth model

random.seed(42)  # reproducibility
s2 = keygen()

m_start = 3
ct_current = encrypt(m_start, s2)
current_noise = abs(ct_current[2])

print(f"Encrypt m = {m_start}, initial noise = {ct_current[2]}")
print()

expected = m_start
dec_val, _ = decrypt(ct_current, s2)

for step in range(1, 12):
    # Multiply by Enc(2): noise grows
    fresh = encrypt(2, s2)
    fresh_n = abs(fresh[2])
    
    # Simulate the multiplication's effect on the encoded value
    expected = (expected * 2) % t
    
    # Noise growth from multiplication
    current_noise = (current_noise * fresh_n * t) // Delta + current_noise + fresh_n + 1
    
    # Simulate decryption: if noise < threshold, we get the right answer
    if current_noise < threshold:
        dec_val = expected
        correct = True
    else:
        # Noise has overwhelmed the message: decryption gives random garbage
        dec_val = randint(0, t - 1)
        correct = (dec_val == expected)  # might be correct by chance
    

print()
print(f'Threshold for correct decryption: {threshold}')
print(f'Once noise exceeds {threshold}, the output is GARBAGE.')
print(f'The ciphertext is irrecoverably corrupted --- not even the key holder can fix it.')

The Fix: Bootstrapping

Bootstrapping (Gentry, 2009) is the technique that rescues FHE from the noise budget wall. The idea:

1. You have a noisy ciphertext $\text{ct}$ about to exceed the budget.

2. Encrypt the secret key $s$ under a fresh key $s'$.

3. Homomorphically evaluate the decryption circuit on $\text{ct}$ using $\text{Enc}_{s'}(s)$.

4. The result is $\text{Enc}_{s'}(m)$ with fresh, low noise.

This "refreshes" the ciphertext. The cost is enormous (evaluating decryption homomorphically is expensive), but it enables unlimited computation depth.

Without bootstrapping, we're stuck with leveled FHE: a fixed number of operations determined at parameter selection time.

# Compare: with vs without bootstrapping
print('=== Without Bootstrapping (Leveled FHE) ===')
noise_no_boot = B
max_mults_no_boot = 0
while noise_no_boot < threshold:
    noise_no_boot = (noise_no_boot * B * t) // Delta + noise_no_boot + B
    if noise_no_boot < threshold:
        max_mults_no_boot += 1

print(f'  Max multiplications before failure: {max_mults_no_boot}')
print(f'  After that, all results are garbage.')
print()

print('=== With Bootstrapping (Full FHE) ===')
boot_noise = B * 2  # noise after bootstrapping (small but not zero)
boot_interval = max_mults_no_boot - 1  # bootstrap before hitting the limit
if boot_interval < 1:
    boot_interval = 1

total_mults = 50
bootstraps_needed = total_mults // boot_interval
print(f'  Bootstrap every {boot_interval} multiplications')
print(f'  To do {total_mults} multiplications: need {bootstraps_needed} bootstraps')
print(f'  Each bootstrap is expensive (~milliseconds to seconds)')
print(f'  But we can compute INDEFINITELY.')
print()

print('=== Trade-off ===')
print(f'  Larger q  --> more noise budget --> fewer bootstraps needed --> faster')
print(f'  Smaller q --> less noise budget --> more bootstraps needed --> slower')
print(f'  But larger q means larger ciphertexts and slower per-operation cost.')

Exercises

Exercise 1: Vary the Modulus $q$

Change $q$ to $65536$ (double the original) and re-run the noise simulation. How many more multiplications can you perform before failure?

# Exercise 1: experiment with different q values
for q_test in [1024, 4096, 32768, 65536, 262144]:
    Delta_test = q_test // t
    threshold_test = Delta_test // 2
    noise_test = B
    mults = 0
    while noise_test < threshold_test and mults < 100:
        noise_test = (noise_test * B * t) // Delta_test + noise_test + B
        if noise_test < threshold_test:
            mults += 1
    print(f'  q = {q_test}, Delta = {Delta_test}, threshold = {threshold_test}, max mults = {mults}')

print()
print('Observation: doubling q roughly adds 1 more multiplication to the budget.')
print('To get 20+ multiplications, you need an astronomically large q.')
print('This is why real FHE libraries use q with hundreds or thousands of bits.')

Exercise 2 (Independent)

1. Modify the plaintext modulus $t$. Try $t = 2$ (binary messages) and $t = 256$. How does the multiplication depth change? Why?

2. Real BFV implementations use $q \approx 2^{200}$ or larger. If the noise growth per multiplication is roughly a factor of $t$, estimate the multiplicative depth for $q = 2^{200}$ and $t = 2^{16}$.

3. Why can't we just make $q$ arbitrarily large to get unlimited depth without bootstrapping? What are the costs?

Summary

Concept	Key Fact
Noise budget	Each ciphertext has a finite tolerance for noise before decryption fails
Addition	Noise grows linearly ($e_1 + e_2$) --- cheap
Multiplication	Noise grows multiplicatively ($\sim e_1 \cdot e_2 \cdot t / \Delta$) --- expensive
Multiplicative depth	Number of sequential multiplications before noise overflow
Larger $q$	More noise budget, but larger ciphertexts and slower operations
Bootstrapping	Refreshes noise to enable unlimited depth, at high per-operation cost
Leveled FHE	No bootstrapping; fixed depth chosen at parameter selection

Noise management is THE central challenge of FHE. Every design decision --- modulus size, plaintext space, relinearization, modulus switching --- is ultimately about squeezing more computation out of a finite noise budget.

---

Back to Module 11: Homomorphic Encryption