11d-bfv-scheme.ipynb

Kernel: SageMath 10.5

Notebook 11d: The BFV Scheme

Module 11: Homomorphic Encryption

---

Motivating Question. BGV encodes the message in the least significant bits and noise as multiples of $t$. Can we flip this around, put the message in the most significant bits and let noise live in the LSBs? This is exactly what BFV (Brakerski/Fan-Vercauteren, 2012) does. The result: a scale-invariant scheme where noise management is simpler, with no explicit modulus chain.

---

Prerequisites. You should be comfortable with:

• BGV encryption, noise growth, and modulus switching (Notebook 11c)

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

• Noise budgets (Notebook 11a)

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

1. Explain how BFV differs from BGV in message encoding.

2. Implement BFV key generation, encryption, and decryption.

3. Perform homomorphic addition and multiplication in BFV.

4. Understand the scale-invariant property and noise budgets.

5. Compare BGV and BFV side by side.

1. BGV vs BFV: Where Does the Message Live?

Bridge from Notebook 11c. In BGV, decryption computes $v = c_0 + c_1 \cdot s = m + t \cdot e$, then takes $v \bmod t$ to recover $m$. The message sits in the low bits and noise is pushed to multiples of $t$. BFV does the opposite.

The key idea in BFV is the scaling factor $\Delta = \lfloor q/t \rfloor$:

	BGV	BFV
Message encoding	$v = m + t \cdot e$	$v = \Delta \cdot m + e$
Where message lives	Least significant bits	Most significant bits
Where noise lives	Multiples of $t$ (MSBs)	Small residual (LSBs)
Decryption	$v \bmod t$	$\lfloor t \cdot v / q \rceil \bmod t$
Noise management	Modulus switching (explicit chain)	Scale-invariant (automatic)

Think of it this way: if $q = 1{,}000{,}003$ and $t = 7$, then $\Delta = 142{,}857$. A message $m = 3$ is encoded as $\Delta \cdot 3 = 428{,}571$. Adding noise $e = 17$ gives $428{,}588$. Since the message contributes $\sim 428{,}000$ and noise only $\sim 17$, the message dominates the upper bits.

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

# The BFV scaling factor
Delta = q // t

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

print(f"=== BFV Parameters ===")
print(f"Ring dimension: n = {n}")
print(f"Plaintext modulus: t = {t}")
print(f"Ciphertext modulus: q = {q}")
print(f"Scaling factor: Δ = ⌊q/t⌋ = {Delta}")
print(f"Noise bound: B = {noise_bound}")
print(f"")
print(f"The message m is encoded as Δ·m ≈ {Delta}·m")
print(f"This 'lifts' the message into the upper bits of q = {q}")

# Visualize where message and noise live in BFV vs BGV
print("=== Message Location: BGV vs BFV ===")
print()
print(f"q = {q}, t = {t}, Δ = {Delta}")
print()
for m in range(t):
    bgv_val = m  # BGV: v = m + t*e, so m lives at the bottom
    bfv_val = Delta * m  # BFV: v = Δ*m + e, so m is scaled up
    bar_bgv = int(40 * bgv_val / q)
    bar_bfv = int(40 * bfv_val / q)
    print(f"  m={m}: BGV v={bgv_val} |{'█' * bar_bgv}{' ' * (40 - bar_bgv)}| (bottom of q)")
    print(f"       BFV v={bfv_val} |{'█' * bar_bfv}{' ' * (40 - bar_bfv)}| (spread across q)")
    print()
print("BFV spreads message values evenly across [0, q),")
print("leaving room for noise between each 'slot'.")

Checkpoint 1. In BFV, the message $m$ is scaled by $\Delta = \lfloor q/t \rfloor$, spreading the $t$ possible message values evenly across $[0, q)$. Noise fills the gaps between these scaled values. Decryption works as long as the noise doesn't push a value past the midpoint between two adjacent slots.

2. BFV Key Generation

BFV key generation is almost identical to BGV, but without the factor of $t$ in the public key error:

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

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

Notice: BGV uses $b = -(a \cdot s + t \cdot e)$ (noise scaled by $t$), but BFV uses just $b = -(a \cdot s + e)$ (raw noise). The factor of $t$ is baked into the message encoding instead.

# Helper functions (same as BGV notebook)
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)
    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))

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

sk, pk = bfv_keygen()
print(f"Secret key s: {centered_coeffs(sk.lift(), q)}")
print(f"\nKey difference from BGV:")
print(f"  BGV: b = -(a·s + t·e)  ← noise scaled by t={t}")
print(f"  BFV: b = -(a·s + e)    ← raw noise")

3. BFV Encryption and Decryption

Encrypt message $m \in R_t$:

• Sample $u, e_1, e_2$ small

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

The message $m$ is scaled up by $\Delta = \lfloor q/t \rfloor$, this is the crucial difference from BGV.

Decrypt ciphertext $(c_0, c_1)$:

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

• Return $\lfloor t \cdot v / q \rceil \bmod t$

Why does this work? After decryption: $$v = \Delta \cdot m + (\text{small noise})$$ Multiplying by $t/q$: $t \cdot v / q \approx t \cdot \Delta \cdot m / q \approx m$ (since $\Delta \approx q/t$). Rounding recovers $m$ exactly.

def bfv_encrypt(m_coeffs, pk):
    """Encrypt a message (list of coefficients mod t) using BFV."""
    b, a = pk
    # Scale message by Delta
    delta_m = Sq(Rq([Delta * (c % t) for c in m_coeffs]))
    u = rand_poly(Sq, 1)       # random ternary
    e1 = rand_poly(Sq, noise_bound)
    e2 = rand_poly(Sq, noise_bound)
    c0 = b * u + e1 + delta_m  # message scaled by Δ
    c1 = a * u + e2
    return (c0, c1)

def bfv_decrypt(ct, s):
    """Decrypt a BFV ciphertext using scale-and-round."""
    c0, c1 = ct
    v = c0 + c1 * s  # v = Δ·m + noise in R_q
    v_coeffs = centered_coeffs(v.lift(), q)
    # Scale by t/q and round
    m_coeffs = [round(RR(t) * RR(c) / RR(q)) % t for c in v_coeffs]
    return m_coeffs

# Test encryption/decryption
msg = [3, 1, 4, 1]
ct = bfv_encrypt(msg, pk)
dec = bfv_decrypt(ct, sk)

print(f"Message:   {msg}")
print(f"Decrypted: {dec}")
print(f"Correct?   {dec == msg}")

# Let's see what's inside the ciphertext
c0, c1 = ct
v = c0 + c1 * sk
v_coeffs = centered_coeffs(v.lift(), q)

print("=== Inside a BFV Ciphertext ===")
print(f"\nv = c0 + c1·s (centered coefficients):")
for i, c in enumerate(v_coeffs):
    expected = Delta * msg[i]
    noise_i = c - expected if i < len(msg) else c
    print(f"  coeff {i}: v[{i}] = {c}  ≈  Δ·m[{i}] = {expected}  +  noise = {noise_i}")

print(f"\nΔ = {Delta}, so each message value contributes ~{Delta} per unit")
print(f"Noise is tiny compared to Δ, rounding recovers the message.")

Misconception alert. "BFV decryption just does $v \bmod t$ like BGV." No! BFV decryption is scale and round: multiply by $t/q$, then round. This is because the message is in the upper bits, not the lower bits. The $\bmod t$ at the end only wraps around the plaintext modulus.

4. Noise Budget in BFV

In BFV, the noise budget measures how much room we have between the noise and the decryption threshold. Specifically:

$$\text{noise budget} = \log_2\left(\frac{\Delta}{2 \cdot \|e\|_\infty}\right) \text{ bits}$$

When the noise exceeds $\Delta/2 = q/(2t)$, the scale-and-round decryption "rounds to the wrong integer" and we get garbage.

def bfv_noise(ct, s, msg):
    """Compute the noise in a BFV ciphertext."""
    c0, c1 = ct
    v = c0 + c1 * s
    v_coeffs = centered_coeffs(v.lift(), q)
    # Noise = v - Δ·m (centered)
    noise_coeffs = []
    for i in range(n):
        m_i = msg[i] if i < len(msg) else 0
        # The "ideal" value for this coefficient
        ideal = Delta * m_i
        # Center the ideal value
        if ideal > q // 2:
            ideal -= q
        noise_coeffs.append(v_coeffs[i] - ideal)
    return noise_coeffs, max(abs(c) for c in noise_coeffs)

def noise_budget(noise_inf):
    """Compute remaining noise budget in bits."""
    if noise_inf == 0:
        return float('inf')
    threshold = Delta // 2  # decryption fails when noise ≥ Δ/2
    if noise_inf >= threshold:
        return 0
    return float(RR(log(RR(threshold) / RR(noise_inf), 2)))

# Measure noise in our fresh ciphertext
noise, noise_inf = bfv_noise(ct, sk, msg)
budget = noise_budget(noise_inf)

print(f"=== Noise Budget ===")
print(f"Noise coefficients: {noise}")
print(f"Noise ∞-norm: {noise_inf}")
print(f"Decryption threshold: Δ/2 = {Delta//2}")
print(f"Noise budget: {budget:.1f} bits")
print(f"\nDecryption fails when noise ≥ {Delta//2}")
print(f"Current noise uses only {100*noise_inf/(Delta//2):.2f}% of the budget")

Checkpoint 2. A fresh BFV ciphertext has a large noise budget because the noise is tiny relative to $\Delta/2$. Each homomorphic operation consumes some of this budget. When it hits zero, decryption fails.

5. Homomorphic Addition

Addition in BFV works the same as in BGV: add ciphertext components.

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

After addition: $v_{\text{sum}} = \Delta(m_1 + m_2) + (e_1 + e_2)$. The noise adds linearly.

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

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

ct1 = bfv_encrypt(msg1, pk)
ct2 = bfv_encrypt(msg2, pk)
ct_sum = bfv_add(ct1, ct2)

dec_sum = bfv_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}")

# Noise comparison
_, n1 = bfv_noise(ct1, sk, msg1)
_, n2 = bfv_noise(ct2, sk, msg2)
_, n_sum = bfv_noise(ct_sum, sk, expected_sum)
print(f"\nNoise: ct1={n1}, ct2={n2}, sum={n_sum}")
print(f"Budget: ct1={noise_budget(n1):.1f}, ct2={noise_budget(n2):.1f}, sum={noise_budget(n_sum):.1f} bits")

# Chain many additions and track the noise budget
messages = [[randint(0, t-1) for _ in range(n)] for _ in range(50)]
cts = [bfv_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 = bfv_add(ct_running, cts[i])
    running_sum = [(running_sum[j] + messages[i][j]) % t for j in range(n)]
    dec = bfv_decrypt(ct_running, sk)
    _, nl = bfv_noise(ct_running, sk, running_sum)
    bgt = noise_budget(nl)
    
    if i in [1, 5, 10, 25, 49]:

print(f"\nAfter 49 additions, budget = {bgt:.1f} bits (started ≈ {noise_budget(bfv_noise(cts[0], sk, messages[0])[1]):.1f} bits).")
print(f"Addition is cheap, noise grows linearly, budget decreases slowly.")

6. Homomorphic Multiplication

This is where BFV truly differs from BGV. When we multiply two BFV ciphertexts:

$$v_1 \cdot v_2 = (\Delta m_1 + e_1)(\Delta m_2 + e_2) = \Delta^2 m_1 m_2 + \Delta(m_1 e_2 + m_2 e_1) + e_1 e_2$$

But we need the result to look like $\Delta \cdot (m_1 m_2) + (\text{small noise})$. So we divide by $\Delta$ (i.e., multiply by $t/q$ and round):

$$d_0 = \lfloor \tfrac{t}{q} \cdot c_0 c_0' \rceil, \quad d_1 = \lfloor \tfrac{t}{q} \cdot (c_0 c_1' + c_1 c_0') \rceil, \quad d_2 = \lfloor \tfrac{t}{q} \cdot c_1 c_1' \rceil$$

This is the scale-invariant property: the rescaling during multiplication keeps the result at the same scale $\Delta$, unlike BGV where you need to explicitly switch moduli.

def poly_rescale(prod_poly, t_val, q_val):
    """Rescale a polynomial: round(t/q * poly) coefficient-wise.
    
    We work over the integers to avoid modular arithmetic artifacts.
    """
    coeffs = centered_coeffs(prod_poly.lift(), q_val)
    # Scale each coefficient by t/q and round
    scaled = [round(RR(t_val) * RR(c) / RR(q_val)) for c in coeffs]
    # Reduce back into R_q
    return Sq(Rq(scaled))

def bfv_mul(ct1, ct2):
    """Homomorphic multiplication in BFV (produces degree-2 ciphertext).
    
    The key difference from BGV: we rescale by t/q to remove one factor of Δ.
    """
    c0, c1 = ct1
    c0p, c1p = ct2
    
    # Compute tensor product components
    d0 = poly_rescale(c0 * c0p, t, q)
    d1_a = c0 * c1p + c1 * c0p
    d1 = poly_rescale(d1_a, t, q)
    d2 = poly_rescale(c1 * c1p, t, q)
    
    return (d0, d1, d2)

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

print("BFV multiplication: tensor product + rescale by t/q")
print("This is the 'scale-invariant' trick, no modulus switching needed.")

# Test multiplication with constant polynomials
msg1 = [2, 0, 0, 0]  # constant 2
msg2 = [3, 0, 0, 0]  # constant 3
expected_prod = [(msg1[0] * msg2[0]) % t] + [0] * (n - 1)  # 6 mod 7 = 6

ct1 = bfv_encrypt(msg1, pk)
ct2 = bfv_encrypt(msg2, pk)
ct_prod = bfv_mul(ct1, ct2)

dec_prod = bfv_decrypt_deg2(ct_prod, sk)

print(f"m1 = {msg1[0]}, m2 = {msg2[0]}")
print(f"Expected product: {msg1[0]}×{msg2[0]} = {msg1[0]*msg2[0]} ≡ {expected_prod[0]} (mod {t})")
print(f"Decrypted: {dec_prod}")
print(f"Correct? {dec_prod == expected_prod}")

# Test with non-trivial polynomial messages
msg1 = [1, 2, 0, 0]  # 1 + 2x
msg2 = [3, 1, 0, 0]  # 3 + x
# Product in Z_t[x]/(x^4+1):
# (1+2x)(3+x) = 3 + x + 6x + 2x^2 = 3 + 7x + 2x^2 = 3 + 0x + 2x^2 (mod 7)
Rt_check.<y> = PolynomialRing(GF(t))
St_check = Rt_check.quotient(y^n + 1, 'Y')
p1 = St_check(Rt_check(msg1))
p2 = St_check(Rt_check(msg2))
p_prod = p1 * p2
expected_poly = [ZZ(c) for c in p_prod.lift().list()]
while len(expected_poly) < n:
    expected_poly.append(0)

ct1 = bfv_encrypt(msg1, pk)
ct2 = bfv_encrypt(msg2, pk)
ct_prod = bfv_mul(ct1, ct2)
dec_prod = bfv_decrypt_deg2(ct_prod, sk)

print(f"m1 = {msg1} → (1 + 2x)")
print(f"m2 = {msg2} → (3 + x)")
print(f"Expected: {expected_poly} → ({p_prod.lift()}) in Z_{t}[x]/(x^{n}+1)")
print(f"Decrypted: {dec_prod}")
print(f"Correct? {dec_prod == expected_poly}")

7. Why "Scale-Invariant"?

The rescaling by $t/q$ during BFV multiplication has a remarkable property: after multiplication, the result is still encoded at scale $\Delta$, with noise that depends only on the input noise, not on the modulus $q$.

Compare:

• BGV: After multiplication, noise grows to $\sim e_1 \cdot e_2 \cdot n$. You must modulus-switch (reduce $q$ to $q'$) to bring noise back down.

• BFV: The $t/q$ rescaling automatically handles the extra $\Delta$ factor. No modulus switching needed.

This is why BFV is called "scale-invariant", the noise-to-message scale ratio stays consistent without manual intervention.

# Demonstrate scale-invariance: noise after multiplication doesn't depend on q
print("=== Scale-Invariance Demonstration ===")
print()
print("If we used different moduli q, the noise budget after multiplication")
print("would still be approximately the same relative to Δ.")
print()

# Compare noise before and after multiplication
msg1 = [3, 0, 0, 0]
msg2 = [5, 0, 0, 0]
expected = [(3 * 5) % t] + [0] * (n - 1)  # 15 mod 7 = 1

ct1 = bfv_encrypt(msg1, pk)
ct2 = bfv_encrypt(msg2, pk)

_, n1 = bfv_noise(ct1, sk, msg1)
_, n2 = bfv_noise(ct2, sk, msg2)

ct_prod = bfv_mul(ct1, ct2)
# Noise for degree-2 ciphertext
d0, d1, d2 = ct_prod
v_prod = d0 + d1 * sk + d2 * sk * sk
v_prod_coeffs = centered_coeffs(v_prod.lift(), q)
noise_prod = [v_prod_coeffs[i] - Delta * expected[i] for i in range(n)]
noise_prod_inf = max(abs(c) for c in noise_prod)

budget_ct1 = noise_budget(n1)
budget_ct2 = noise_budget(n2)
budget_prod = noise_budget(noise_prod_inf)

print(f"Input ct1: noise = {n1}, budget = {budget_ct1:.1f} bits")
print(f"Input ct2: noise = {n2}, budget = {budget_ct2:.1f} bits")
print(f"Product:   noise = {noise_prod_inf}, budget = {budget_prod:.1f} bits")
print(f"\nMultiplication consumed ~{budget_ct1 - budget_prod:.1f} bits of noise budget.")
print(f"\nIn BGV, we'd need to modulus-switch here to reclaim budget.")
print(f"In BFV, the rescaling by t/q already did the equivalent work.")

# Side-by-side comparison of the two approaches
print("=== BGV vs BFV: Multiplication Pipeline ===")
print()
print("BGV:")
print("  ct1 × ct2  →  tensor product  →  noise ~e1·e2·n  →  modulus switch q→q'  →  noise reduced")
print("  (message in LSBs, noise in MSBs as multiples of t)")
print()
print("BFV:")
print("  ct1 × ct2  →  tensor product  →  rescale by t/q  →  noise automatically managed")
print("  (message in MSBs scaled by Δ, noise in LSBs)")
print()
print("The t/q rescaling in BFV multiplication serves the same")
print("purpose as modulus switching in BGV, but is built into")
print("the multiplication operation itself.")

Checkpoint 3. The "scale-invariant" property means: after BFV multiplication, the noise level relative to $\Delta$ is predictable and doesn't depend on $q$. In BGV, you must explicitly manage the modulus chain; in BFV, the rescaling is baked into the multiplication.

8. A Mini-Computation: $f(a, b) = a \cdot b + a$

Let's run the same computation from the BGV notebook to see BFV in action.

# 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 ≡ 1 (mod 7)

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()

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

# Multiply (degree-2 ciphertext)
ct_ab = bfv_mul(ct_a, ct_b)
dec_ab = bfv_decrypt_deg2(ct_ab, sk)
print(f"Step 2: Enc(a) × Enc(b) → degree-2 ct, decrypts to {dec_ab}")

# For the addition, we need a degree-1 ciphertext
# In a full implementation, relinearization converts degree-2 back to degree-1
# We simulate by re-encrypting the product
ab_val = [(a_val[0] * b_val[0]) % t] + [0] * (n - 1)
ct_ab_relin = bfv_encrypt(ab_val, pk)  # simulating relinearization

# Add Enc(a*b) + Enc(a)
ct_result = bfv_add(ct_ab_relin, ct_a)
dec_result = bfv_decrypt(ct_result, sk)
print(f"Step 3: Enc(a·b) + Enc(a) → decrypts to {dec_result}")
print(f"Expected: {expected}")
print(f"Correct? {dec_result == expected}")
print(f"\nf(3, 4) = 3×4 + 3 = 15 ≡ 1 (mod 7) ✓")

9. Comprehensive Comparison: BGV vs BFV

Now that we've implemented both, let's compare them systematically.

print("="*75)
print("BGV vs BFV: Comprehensive Comparison")
print("="*75)
print()

comparison = [
    ("Full name",
     "Brakerski-Gentry-Vaikuntanathan",
     "Brakerski/Fan-Vercauteren"),
    ("Year", "2011", "2012"),
    ("Security basis", "Ring-LWE", "Ring-LWE"),
    ("Message encoding",
     "v = m + t·e (LSBs)",
     "v = Δ·m + e (MSBs)"),
    ("Decryption",
     "v mod t",
     "round(t·v/q) mod t"),
    ("Noise management",
     "Explicit modulus switching",
     "Scale-invariant (auto)"),
    ("Requires modulus chain?",
     "Yes (q_L > ... > q_0)",
     "No (single modulus)"),
    ("Multiplication",
     "Tensor + relin + mod switch",
     "Tensor + rescale(t/q) + relin"),
    ("Best for",
     "Depth-optimized circuits",
     "Simpler implementation"),
    ("Libraries",
     "HElib",
     "Microsoft SEAL, OpenFHE"),
]

for label, bgv, bfv in comparison:
    print(f"  {label:.<28s} BGV: {bgv}")
    print(f"  {'':28s} BFV: {bfv}")
    print()

# When to choose which?
print("=== Decision Guide: BGV vs BFV ===")
print()
print("Choose BGV when:")
print("  • Circuit depth is known at compile time")
print("  • You need maximum efficiency for deep circuits")
print("  • You're working with HElib or similar BGV-native libraries")
print("  • You want fine-grained control over modulus chain")
print()
print("Choose BFV when:")
print("  • Simplicity of implementation matters")
print("  • Circuit depth varies or is unknown")
print("  • You're using Microsoft SEAL or OpenFHE")
print("  • You want integer arithmetic without managing a modulus chain")
print()
print("In practice, BGV and BFV have very similar performance.")
print("The choice often comes down to library availability.")

Crypto foreshadowing. Both BGV and BFV work with integer plaintexts, messages are elements of $\mathbb{Z}_t[x]/(x^n+1)$. But what about real-number computations like machine learning inference? The next notebook introduces CKKS, which encodes approximate real numbers and allows controlled loss of precision, a paradigm shift from exact arithmetic.

10. Exercises

Exercise 1 (Worked): Decryption by Hand

Problem. If $q = 100$, $t = 5$, so $\Delta = 20$. A ciphertext decrypts to the value $v = 63$. What is the plaintext $m$?

Solution:

# Exercise 1: Worked solution
q_ex, t_ex, v_ex = 100, 5, 63
Delta_ex = q_ex // t_ex  # = 20

# BFV decryption: round(t * v / q) mod t
scaled = RR(t_ex) * RR(v_ex) / RR(q_ex)  # 5 * 63 / 100 = 3.15
rounded = round(scaled)  # round(3.15) = 3
m_recovered = rounded % t_ex  # 3 mod 5 = 3

print(f"q = {q_ex}, t = {t_ex}, Δ = ⌊q/t⌋ = {Delta_ex}")
print(f"v = {v_ex}")
print(f"")
print(f"Step 1: t·v/q = {t_ex}·{v_ex}/{q_ex} = {float(scaled):.2f}")
print(f"Step 2: round({float(scaled):.2f}) = {rounded}")
print(f"Step 3: {rounded} mod {t_ex} = {m_recovered}")
print(f"")
print(f"Plaintext m = {m_recovered}")
print(f"")
print(f"Check: Δ·m = {Delta_ex}·{m_recovered} = {Delta_ex * m_recovered}, so noise = v - Δ·m = {v_ex - Delta_ex * m_recovered}")
print(f"Noise {abs(v_ex - Delta_ex * m_recovered)} < Δ/2 = {Delta_ex // 2}? {abs(v_ex - Delta_ex * m_recovered) < Delta_ex // 2}")

Exercise 2 (Guided): Exhausting the Noise Budget

Problem. Encrypt a message and repeatedly multiply it by itself (squaring). Track the noise budget after each squaring. How many squarings before decryption fails?

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# TODO 1: Encrypt the constant message m = 2
# msg_ex = [2, 0, 0, 0]
# ct_ex = bfv_encrypt(msg_ex, pk)
# running_msg = list(msg_ex)

# TODO 2: Repeatedly square (multiply ct with itself) and check
# Hint: After degree-2 multiplication, you need bfv_decrypt_deg2
# But for chaining, you'd need relinearization (which we don't have)
# Instead, try: compute m^2 plaintext, re-encrypt, then multiply again
#
# for i in range(1, 10):
#     new_val = [(running_msg[0]^2) % t] + [0] * (n-1)
#     ct_ex = bfv_encrypt(new_val, pk)
#     running_msg = new_val
#     _, nl = bfv_noise(ct_ex, sk, running_msg)
#     bgt = noise_budget(nl)
#     print(f"After squaring {i}: m = {running_msg[0]}, noise = {nl}, budget = {bgt:.1f} bits")
#
# TODO 3: At what point would budget reach 0 in a real implementation
# without re-encryption? (Think about how noise grows with each mult.)

Exercise 3 (Independent): BFV with Different Parameters

Problem.

1. Change the plaintext modulus to $t = 2$ (binary messages). How does this affect $\Delta$ and the noise budget of a fresh ciphertext?

2. What happens if you use $t = q - 1$ (almost no scaling)? Can you still decrypt correctly?

3. For a circuit of multiplicative depth $d$, derive a rough lower bound on $\log_2(q)$ in terms of $d$, $t$, and the initial noise $B$.

# Exercise 3: write your solution here

Summary

Concept	Key Fact
Scaling factor	$\Delta = \lfloor q/t \rfloor$, message scaled into MSBs
BFV encryption	$c_0 = b \cdot u + e_1 + \Delta \cdot m$, noise in LSBs
BFV decryption	$\lfloor t \cdot v/q \rceil \bmod t$, scale-and-round
Noise budget	$\log_2(\Delta / (2 |e|_\infty))$ bits; zero means garbled output
Multiplication	Tensor product then rescale by $t/q$, removes one factor of $\Delta$
Scale-invariant	Noise after multiplication doesn't depend on $q$; no modulus chain needed
BGV vs BFV	Same security, different noise encoding; BFV simpler, BGV more flexible

BFV flips the BGV encoding: message in the MSBs, noise in the LSBs. The scale-and-round decryption and the $t/q$ rescaling during multiplication make BFV "scale-invariant", noise management is automatic rather than requiring an explicit modulus chain.

---

Next: 11e: CKKS: Approximate Arithmetic