11c-bgv-scheme.ipynb

Kernel: SageMath 10.5

Notebook 11c: The BGV Scheme

Module 11: Homomorphic Encryption

---

Motivating Question. Paillier gives us unlimited additions but no multiplications. How do we get both? The BGV scheme (Brakerski-Gentry-Vaikuntanathan, 2011) is built on Ring-LWE and supports both addition and multiplication, but each operation adds noise. The key innovation: modulus switching controls this noise by scaling down the ciphertext modulus, trading precision for reduced noise.

---

Prerequisites. You should be comfortable with:

• Partial homomorphism and why both operations are needed (Notebook 11b)

• Ring-LWE and polynomial rings $\mathbb{Z}_q[x]/(x^n+1)$ (Module 08)

• Noise growth concepts (Notebook 11a)

Learning objectives. By the end of this notebook you will be able to:

1. Set up the polynomial ring for BGV encryption.

2. Encrypt and decrypt messages using the BGV scheme.

3. Perform homomorphic addition and observe linear noise growth.

4. Perform homomorphic multiplication and observe quadratic noise growth.

5. Apply modulus switching to reduce noise after multiplication.

1. The BGV Setup: Polynomial Rings

Bridge from Notebook 11b. Paillier and ElGamal work with integers. BGV works with polynomials, specifically, polynomials in the ring $R_q = \mathbb{Z}_q[x]/(x^n+1)$. Why the switch? Two reasons. First, security: each polynomial encodes $n$ coefficients, giving us a lattice of dimension $n$, much harder to attack than the 1-dimensional integer LWE from Module 08. This is exactly the Ring-LWE assumption from Notebook 08e. Second, efficiency: polynomial multiplication in $R_q$ can be done in $O(n \log n)$ via NTT/FFT, making operations on $n$ values nearly as fast as on one. The noise encoding $v = m + t \cdot e$ is analogous to Paillier's $g^m \cdot r^n$, both hide the message inside an algebraic structure that supports homomorphic operations.

Parameters:

• $n$: ring dimension (power of 2)

• $t$: plaintext modulus (messages live in $R_t = \mathbb{Z}_t[x]/(x^n+1)$)

• $q$: ciphertext modulus (ciphertexts live in $R_q$, with $q \gg t$)

• $\sigma$: noise standard deviation

# BGV parameters (toy-sized for demonstration)
n = 4           # polynomial degree (ring dimension)
t = 7           # plaintext modulus
q = 1000003     # ciphertext modulus (large prime)
noise_bound = 3 # |e_i| ≤ noise_bound

# Polynomial rings
Rq.<x> = PolynomialRing(GF(q))
Phi = x^n + 1  # cyclotomic polynomial
Sq = Rq.quotient(Phi, 'X')  # R_q = Z_q[x]/(x^n+1)

Rt.<y> = PolynomialRing(GF(t))
St = Rt.quotient(y^n + 1, 'Y')  # R_t = Z_t[x]/(x^n+1)

print(f"=== BGV Parameters ===")
print(f"Ring dimension: n = {n}")
print(f"Plaintext modulus: t = {t}")
print(f"Ciphertext modulus: q = {q}")
print(f"Noise bound: B = {noise_bound}")
print(f"Ring: R_q = Z_{q}[x]/(x^{n}+1)")
print(f"Plaintext space: R_t = Z_{t}[x]/(x^{n}+1)")

# Helper functions for polynomial operations
def rand_poly(ring, bound):
    """Random polynomial with small coefficients in [-bound, bound]."""
    coeffs = [randint(-bound, bound) for _ in range(n)]
    return ring(coeffs)

def centered_coeffs(poly, mod):
    """Get centered coefficients (in [-mod/2, mod/2)) of a polynomial."""
    coeffs = []
    for c in poly.list():
        c_int = ZZ(c)
        if c_int > mod // 2:
            c_int -= mod
        coeffs.append(c_int)
    # Pad to n coefficients
    while len(coeffs) < n:
        coeffs.append(0)
    return coeffs

def noise_norm(poly, mod):
    """Infinity norm of centered coefficients."""
    return max(abs(c) for c in centered_coeffs(poly, mod))

# Demo: polynomials in the ring
a_demo = Sq(Rq([3, -1, 2, 0]))
b_demo = Sq(Rq([1, 2, -1, 1]))
print(f"a = {a_demo.lift()}")
print(f"b = {b_demo.lift()}")
print(f"a + b = {(a_demo + b_demo).lift()}")
print(f"a × b = {(a_demo * b_demo).lift()} (mod x^{n}+1, mod {q})")

2. BGV Encryption and Decryption

Key Generation:

• Secret key: $s \in R_q$ with small coefficients

• Public key: $(b, a)$ where $a \xleftarrow{$} R_q$, $e \leftarrow \chi$ (small noise), $b = -(a \cdot s + t \cdot e)$

Encrypt message $m \in R_t$:

• Sample $u, e_1, e_2$ small

• $\text{ct} = (c_0, c_1) = (b \cdot u + t \cdot e_1 + m, \; a \cdot u + t \cdot e_2)$

Decrypt ciphertext $(c_0, c_1)$:

• Compute $v = c_0 + c_1 \cdot s \pmod{q}$

• Return $v \bmod t$

Why does this work? $v = m + t \cdot (\text{noise terms})$, so $v \bmod t = m$ as long as the noise is small enough.

def bgv_keygen():
    """Generate BGV secret and public key."""
    s = rand_poly(Sq, 1)  # secret key: ternary coefficients
    a = Sq(Rq([randint(0, q-1) for _ in range(n)]))  # random
    e = rand_poly(Sq, noise_bound)  # small noise
    b = -(a * s + Sq(Rq([t])) * e)  # b = -(a*s + t*e)
    pk = (b, a)
    return s, pk

def bgv_encrypt(m_coeffs, pk):
    """Encrypt a message (list of coefficients mod t)."""
    b, a = pk
    m = Sq(Rq(m_coeffs))  # embed message in R_q
    u = rand_poly(Sq, 1)  # random ternary
    e1 = rand_poly(Sq, noise_bound)
    e2 = rand_poly(Sq, noise_bound)
    t_elem = Sq(Rq([t]))
    c0 = b * u + t_elem * e1 + m
    c1 = a * u + t_elem * e2
    return (c0, c1)

def bgv_decrypt(ct, s):
    """Decrypt a BGV ciphertext."""
    c0, c1 = ct
    v = c0 + c1 * s  # v = m + t*(noise) in R_q
    # Reduce coefficients mod t
    v_coeffs = centered_coeffs(v.lift(), q)
    m_coeffs = [c % t for c in v_coeffs]
    return m_coeffs

# Generate keys
sk, pk = bgv_keygen()
print(f"Secret key s: {centered_coeffs(sk.lift(), q)}")

# Encrypt a message
msg = [3, 1, 4, 1]  # message coefficients (mod t=7)
ct = bgv_encrypt(msg, pk)
print(f"\nMessage: {msg}")
print(f"Ciphertext c0: {centered_coeffs(ct[0].lift(), q)[:4]}")
print(f"Ciphertext c1: {centered_coeffs(ct[1].lift(), q)[:4]}")

# Decrypt
dec = bgv_decrypt(ct, sk)
print(f"\nDecrypted: {dec}")
print(f"Original:  {msg}")
print(f"Correct? {dec == msg}")

# Let's peek at the noise
def bgv_noise(ct, s, msg):
    """Compute the noise in a ciphertext."""
    c0, c1 = ct
    v = c0 + c1 * s  # v = m + t*noise
    v_coeffs = centered_coeffs(v.lift(), q)
    m_coeffs_padded = msg + [0] * (n - len(msg))
    noise_coeffs = [(v_coeffs[i] - m_coeffs_padded[i]) for i in range(n)]
    return noise_coeffs, max(abs(c) for c in noise_coeffs)

noise, noise_inf = bgv_noise(ct, sk, msg)
print(f"Noise polynomial: {noise}")
print(f"Noise infinity norm: {noise_inf}")
print(f"Each noise coefficient is divisible by t={t}: {all(c % t == 0 for c in noise)}")
print(f"\nNoise budget: noise must be < q/2 = {q//2}")
print(f"Current noise: {noise_inf} (plenty of room!)")

Checkpoint 1. The noise in a fresh BGV ciphertext is roughly $t \cdot B$ where $B$ is the noise bound. Decryption works as long as the total noise stays below $q/2$. Every homomorphic operation increases the noise.

3. Homomorphic Addition

Adding two BGV ciphertexts is simple: add component-wise.

$$(c_0, c_1) + (c_0', c_1') = (c_0 + c_0', c_1 + c_1')$$

The noise adds: $e_{\text{sum}} \approx e_1 + e_2$.

def bgv_add(ct1, ct2):
    """Homomorphic addition."""
    return (ct1[0] + ct2[0], ct1[1] + ct2[1])

# Encrypt two messages and add
msg1 = [3, 1, 4, 1]
msg2 = [2, 6, 5, 3]
expected_sum = [(msg1[i] + msg2[i]) % t for i in range(n)]

ct1 = bgv_encrypt(msg1, pk)
ct2 = bgv_encrypt(msg2, pk)
ct_sum = bgv_add(ct1, ct2)

dec_sum = bgv_decrypt(ct_sum, sk)

print(f"m1 = {msg1}")
print(f"m2 = {msg2}")
print(f"Expected sum (mod {t}): {expected_sum}")
print(f"Decrypted sum: {dec_sum}")
print(f"Correct? {dec_sum == expected_sum}")

# Check noise growth
_, n1 = bgv_noise(ct1, sk, msg1)
_, n2 = bgv_noise(ct2, sk, msg2)
_, n_sum = bgv_noise(ct_sum, sk, expected_sum)
print(f"\nNoise in ct1: {n1}")
print(f"Noise in ct2: {n2}")
print(f"Noise in ct_sum: {n_sum}")
print(f"Noise grows roughly additively: {n_sum} ≈ {n1} + {n2} = {n1+n2}")

# Chain many additions
messages = [[randint(0, t-1) for _ in range(n)] for _ in range(50)]
cts = [bgv_encrypt(m, pk) for m in messages]

ct_running = cts[0]
running_sum = list(messages[0])


for i in range(1, len(messages)):
    ct_running = bgv_add(ct_running, cts[i])
    running_sum = [(running_sum[j] + messages[i][j]) % t for j in range(n)]
    dec = bgv_decrypt(ct_running, sk)
    _, noise_level = bgv_noise(ct_running, sk, running_sum)
    budget_pct = 100 * noise_level / (q // 2)
    
    if i in [1, 5, 10, 25, 49]:

print(f"\nAfter 49 additions: still only {budget_pct:.2f}% of noise budget used.")
print(f"Addition is cheap in BGV, noise grows linearly.")

4. Homomorphic Multiplication (Simplified)

Multiplication is harder. The product of two degree-1 ciphertexts gives a degree-2 ciphertext:

If $\text{ct}_1 = (c_0, c_1)$ decrypts as $c_0 + c_1 \cdot s$ and $\text{ct}_2 = (c_0', c_1')$ decrypts as $c_0' + c_1' \cdot s$, then:

$$(c_0 + c_1 s)(c_0' + c_1' s) = c_0 c_0' + (c_0 c_1' + c_1 c_0') s + c_1 c_1' s^2$$

This gives a "degree-2" ciphertext $(d_0, d_1, d_2)$ that decrypts with $d_0 + d_1 s + d_2 s^2$.

Relinearization converts this back to a standard degree-1 ciphertext (using a special evaluation key).

def bgv_mul_raw(ct1, ct2):
    """Homomorphic multiplication (produces degree-2 ciphertext)."""
    c0, c1 = ct1
    c0p, c1p = ct2
    d0 = c0 * c0p
    d1 = c0 * c1p + c1 * c0p
    d2 = c1 * c1p
    return (d0, d1, d2)

def bgv_decrypt_deg2(ct, s):
    """Decrypt a degree-2 ciphertext."""
    d0, d1, d2 = ct
    v = d0 + d1 * s + d2 * s * s  # d0 + d1*s + d2*s²
    v_coeffs = centered_coeffs(v.lift(), q)
    m_coeffs = [c % t for c in v_coeffs]
    return m_coeffs

# Multiply two ciphertexts
msg1 = [2, 0, 0, 0]  # just the constant 2
msg2 = [3, 0, 0, 0]  # just the constant 3
expected_prod = [(msg1[0] * msg2[0]) % t] + [0] * (n-1)  # 6 mod 7 = 6

ct1 = bgv_encrypt(msg1, pk)
ct2 = bgv_encrypt(msg2, pk)
ct_prod = bgv_mul_raw(ct1, ct2)

dec_prod = bgv_decrypt_deg2(ct_prod, sk)

print(f"m1 = {msg1}")
print(f"m2 = {msg2}")
print(f"Expected product (mod {t}): {expected_prod}")
print(f"Decrypted product: {dec_prod}")
print(f"Correct? {dec_prod == expected_prod}")
print(f"\nMultiplication works! But the ciphertext grew from 2 to 3 elements.")

# Check noise after multiplication
d0, d1, d2 = ct_prod
v = d0 + d1 * sk + d2 * sk * sk
v_coeffs = centered_coeffs(v.lift(), q)
noise_mul = [(v_coeffs[i] - expected_prod[i]) for i in range(n)]
noise_mul_norm = max(abs(c) for c in noise_mul)

# Compare with addition noise
_, noise_ct1 = bgv_noise(ct1, sk, msg1)
_, noise_ct2 = bgv_noise(ct2, sk, msg2)

print(f"Noise in ct1: {noise_ct1}")
print(f"Noise in ct2: {noise_ct2}")
print(f"Noise after multiplication: {noise_mul_norm}")
print(f"Noise after addition would be: ~{noise_ct1 + noise_ct2}")
print(f"\nMultiplication noise is MUCH larger than addition noise.")
print(f"Rough bound: mul noise ≈ n × noise1 × noise2 / t")
print(f"This is why multiplications consume noise budget much faster.")

Misconception alert. "Multiplication noise is just $e_1 \times e_2$." It's more complex in the ring setting, cross terms and the ring dimension $n$ contribute. The key takeaway: multiplication noise grows quadratically while addition noise grows linearly.

5. Modulus Switching: The BGV Innovation

BGV's key insight: after a multiplication, scale down the ciphertext from modulus $q$ to a smaller modulus $q'$. This reduces the noise (at the cost of a smaller modulus for future operations).

Idea: If $\text{ct} = (c_0, c_1)$ has noise $e$ under modulus $q$, then $\text{ct}' = \text{round}(q'/q \cdot \text{ct})$ has noise roughly $e \cdot q'/q$ under modulus $q'$.

By choosing a chain of decreasing moduli $q_L > q_{L-1} > \ldots > q_0$, each multiplication's noise is managed before the next operation.

# Demonstrate modulus switching concept with scalars
# (Polynomial modulus switching is the same idea, applied coefficient-wise)

q_large = 1000003
q_small = 10007

# A ciphertext value with noise
m_demo = 42
noise_demo = 3500  # large noise
ct_val = m_demo + t * noise_demo  # v = m + t*e under q_large

print(f"=== Modulus Switching (scalar demo) ===")
print(f"Original modulus: q = {q_large}")
print(f"Target modulus: q' = {q_small}")
print(f"Message: m = {m_demo}")
print(f"Noise: e = {noise_demo}, so t*e = {t * noise_demo}")
print(f"Ciphertext value: v = {ct_val}")

# Scale down: v' = round(q'/q * v)
v_scaled = round(RR(q_small) / RR(q_large) * ct_val)
# Adjust to preserve v mod t
# We need v' ≡ v (mod t), so adjust by at most t/2
diff = (ct_val - v_scaled) % t
if diff > t // 2:
    diff -= t
v_adjusted = v_scaled + diff

new_noise = (v_adjusted - m_demo) // t

print(f"\nScaled value: v' ≈ {v_adjusted}")
print(f"New noise: e' = {new_noise}")
print(f"v' mod t = {v_adjusted % t} (should be {m_demo % t})")
print(f"\nNoise reduction: {noise_demo} → {new_noise} (factor {RR(noise_demo)/RR(abs(new_noise)):.1f}x)")
print(f"Modulus reduction: {q_large} → {q_small} (factor {RR(q_large)/RR(q_small):.1f}x)")
print(f"\nNoise and modulus shrink by roughly the same factor!")

Checkpoint 2. Modulus switching trades modulus size for noise reduction. After $L$ multiplications, we need a chain of $L$ moduli. This is why BGV is called a leveled scheme, the number of multiplications is fixed at setup time by the modulus chain length.

# Visualize the modulus chain for a depth-4 computation
print("=== Leveled BGV: Modulus Chain ===")
print()
print("For a circuit of multiplicative depth L, we need L+1 moduli:")
print()

L = 4  # multiplicative depth
q_chain = []
q_current = 10^15  # start with a large modulus
for i in range(L + 1):
    q_chain.append(int(q_current))
    q_current //= 100  # each level ~100x smaller

q_chain.reverse()  # q_0 < q_1 < ... < q_L

for i in range(L, -1, -1):
    event = "Fresh ciphertext" if i == L else f"After multiplication #{L-i} + mod switch"
    print(f"{i} | {q_chain[i]:>20,} | {RR(log(q_chain[i], 2)):.1f} bits | {event}")

print(f"\nAt each level, noise shrinks proportionally to the modulus drop.")
print(f"After {L} multiplications, we've 'used up' the modulus chain.")

6. Putting It Together: A Mini-Computation

Let's compute $f(a, b) = a \cdot b + a$ on encrypted data.

# Compute f(a, b) = a*b + a on encrypted data
a_val = [3, 0, 0, 0]  # a = 3
b_val = [4, 0, 0, 0]  # b = 4
expected = [(a_val[0] * b_val[0] + a_val[0]) % t] + [0] * (n-1)  # 3*4 + 3 = 15 mod 7 = 1

print(f"Computing f(a, b) = a × b + a")
print(f"a = {a_val[0]}, b = {b_val[0]}")
print(f"Expected: {a_val[0]} × {b_val[0]} + {a_val[0]} = {a_val[0] * b_val[0] + a_val[0]} ≡ {expected[0]} (mod {t})")
print()

# Step 1: Encrypt
ct_a = bgv_encrypt(a_val, pk)
ct_b = bgv_encrypt(b_val, pk)
print("Step 1: Encrypted a and b")

# Step 2: Multiply (produces degree-2 ciphertext)
ct_ab_raw = bgv_mul_raw(ct_a, ct_b)
print("Step 2: Computed Enc(a) × Enc(b) → degree-2 ciphertext")

# Step 3: Decrypt the product (using degree-2 decryption)
# In a full implementation, we'd relinearize first
dec_ab = bgv_decrypt_deg2(ct_ab_raw, sk)
print(f"Step 3: Dec(a×b) = {dec_ab}")

# For the addition, we need to convert back to degree-1
# We'll simulate by using the known product
ab_val = [(a_val[0] * b_val[0]) % t] + [0] * (n-1)
ct_ab = bgv_encrypt(ab_val, pk)  # re-encrypt for demo

# Step 4: Add Enc(a*b) + Enc(a)
ct_result = bgv_add(ct_ab, ct_a)
dec_result = bgv_decrypt(ct_result, sk)
print(f"Step 4: Dec(a×b + a) = {dec_result}")
print(f"Expected: {expected}")
print(f"Correct? {dec_result == expected}")
print(f"\nWe computed f(3, 4) = 3×4 + 3 = 15 ≡ 1 (mod 7) on encrypted data!")

Checkpoint 3. Even with our simplified implementation, you can see the BGV pipeline: encrypt → multiply (noise grows) → modulus switch (noise shrinks) → add (noise grows a little) → decrypt. A full implementation would include relinearization keys and modulus switching on polynomial ciphertexts.

Crypto foreshadowing. The next notebook covers BFV, a closely related scheme with a simpler noise management approach: instead of modulus switching, BFV scales the message into the upper bits of the modulus, giving "scale-invariant" noise behavior.

7. Exercises

Exercise 1 (Worked): Addition Chain

Problem. Encrypt the values 1, 2, 3, 4, 5 (as constant polynomials) and compute their sum homomorphically. Verify the result is $15 \bmod 7 = 1$.

Solution:

# Exercise 1: Worked solution
values = [1, 2, 3, 4, 5]
cts_ex = [bgv_encrypt([v, 0, 0, 0], pk) for v in values]

ct_total = cts_ex[0]
for ct in cts_ex[1:]:
    ct_total = bgv_add(ct_total, ct)

dec_total = bgv_decrypt(ct_total, sk)
expected_total = [sum(values) % t] + [0] * (n-1)

print(f"Values: {values}")
print(f"Sum: {sum(values)} ≡ {sum(values) % t} (mod {t})")
print(f"Decrypted: {dec_total}")
print(f"Correct? {dec_total == expected_total}")

Exercise 2 (Guided): Noise Budget Tracking

Problem. Encrypt a message and repeatedly add it to itself. Track the noise after each addition. At what point does the noise exceed $q/4$?

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# TODO 1: Encrypt the message [1, 0, 0, 0]
# msg_ex = [1, 0, 0, 0]
# ct_ex = bgv_encrypt(msg_ex, pk)

# TODO 2: Repeatedly add ct_ex to itself, tracking noise
# ct_running = ct_ex
# running_msg = list(msg_ex)
# for i in range(1, 200):
#     ct_running = bgv_add(ct_running, ct_ex)
#     running_msg = [(running_msg[j] + msg_ex[j]) % t for j in range(n)]
#     _, noise_level = bgv_noise(ct_running, sk, running_msg)
#     if noise_level > q // 4:
#         print(f"Noise exceeded q/4 after {i} additions")
#         print(f"Noise: {noise_level}, Budget: {q // 4}")
#         break
#     if i % 20 == 0:
#         print(f"After {i} additions: noise = {noise_level}")

Exercise 3 (Independent): Modulus Chain Design

Problem.

1. For a circuit that requires 3 multiplications and 10 additions, design a modulus chain (choose the initial $q$ and the scaling factors).

2. If initial noise is $B = 10$ and each multiplication increases noise by a factor of $100n = 400$, what is the minimum initial modulus $q$ needed?

3. How does increasing the ring dimension $n$ affect the noise growth per multiplication?

# Exercise 3: write your solution here

Summary

Concept	Key Fact
BGV encryption	Ciphertext $(c_0, c_1) \in R_q^2$ decrypts as $c_0 + c_1 \cdot s \bmod t$
Noise encoding	Noise is a multiple of $t$: $v = m + t \cdot e$
Addition	Add components; noise adds: $e_{\text{sum}} = e_1 + e_2$ (linear)
Multiplication	Tensor product; noise multiplies: $e_{\text{prod}} \sim e_1 \cdot e_2 \cdot n$ (quadratic)
Modulus switching	Scale from $q$ to $q'$; noise drops by factor $q'/q$
Leveled FHE	Pre-set modulus chain for $L$ multiplications; no bootstrapping needed

BGV achieves both addition and multiplication by building on Ring-LWE. The price is noise growth, managed by modulus switching. For circuits of known depth, this is very efficient, and avoids the expense of bootstrapping.

---

Next: 11d: The BFV Scheme