11b-partially-homomorphic-schemes.ipynb

Kernel: SageMath 10.5

Notebook 11b: Partially Homomorphic Schemes

Module 11: Homomorphic Encryption

---

Motivating Question. Before FHE existed, cryptographers knew about schemes that were homomorphic for one operation, either addition or multiplication, but not both. Can we still do useful things with just one operation? Absolutely: Paillier (additive) lets you compute sums and averages on encrypted data, which is enough for voting, auctions, and basic statistics.

---

Prerequisites. You should be comfortable with:

• The FHE dream and noise concepts (Notebook 11a)

• RSA encryption basics (Module 04)

• Discrete logarithm groups (Module 05)

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

1. Demonstrate RSA's multiplicative homomorphism.

2. Implement Paillier encryption and its additive homomorphism.

3. Show ElGamal's multiplicative homomorphism.

4. Understand why partial homomorphism is useful but not sufficient for general computation.

5. See why we need both operations for FHE.

1. RSA: Multiplicatively Homomorphic

Bridge from Notebook 11a. We said FHE needs both addition and multiplication on ciphertexts. Let's start with schemes that give us just one. RSA, the oldest public-key scheme, turns out to be multiplicatively homomorphic!

Recall textbook RSA:

• Public key: $(n, e)$, Private key: $d$

• $\text{Enc}(m) = m^e \bmod n$

• $\text{Dec}(c) = c^d \bmod n$

The homomorphic property: $$\text{Enc}(m_1) \cdot \text{Enc}(m_2) = m_1^e \cdot m_2^e = (m_1 \cdot m_2)^e = \text{Enc}(m_1 \cdot m_2) \pmod{n}$$

# RSA key generation (small primes for demo)
p_rsa, q_rsa = 61, 53
n_rsa = p_rsa * q_rsa
phi = (p_rsa - 1) * (q_rsa - 1)
e_rsa = 17  # public exponent
d_rsa = inverse_mod(e_rsa, phi)  # private exponent

print(f"RSA key generation:")
print(f"  p = {p_rsa}, q = {q_rsa}, n = {n_rsa}")
print(f"  e = {e_rsa}, d = {d_rsa}")

def rsa_enc(m, e, n):
    return power_mod(m, e, n)

def rsa_dec(c, d, n):
    return power_mod(c, d, n)

# Encrypt two messages
m1, m2 = 7, 5
c1 = rsa_enc(m1, e_rsa, n_rsa)
c2 = rsa_enc(m2, e_rsa, n_rsa)

print(f"\nm1 = {m1}, Enc(m1) = {c1}")
print(f"m2 = {m2}, Enc(m2) = {c2}")

# Homomorphic multiplication
c_prod = (c1 * c2) % n_rsa
dec_prod = rsa_dec(c_prod, d_rsa, n_rsa)

print(f"\nEnc(m1) × Enc(m2) = {c_prod}")
print(f"Dec(c_prod) = {dec_prod}")
print(f"m1 × m2 = {m1 * m2}")
print(f"Match? {dec_prod == m1 * m2}")
print(f"\nRSA is multiplicatively homomorphic, no key needed for multiplication!")

# Chain multiple multiplications
messages = [3, 5, 7, 11]
ciphertexts = [rsa_enc(m, e_rsa, n_rsa) for m in messages]

# Multiply all ciphertexts
c_all = 1
for c in ciphertexts:
    c_all = (c_all * c) % n_rsa

dec_all = rsa_dec(c_all, d_rsa, n_rsa)
product = 1
for m in messages:
    product *= m

print(f"Messages: {messages}")
print(f"Product: {product}")
print(f"Homomorphic product (decrypted): {dec_all}")
print(f"Match? {dec_all == product % n_rsa}")
print(f"\nNote: result is mod n = {n_rsa}, so overflow wraps around.")
print(f"RSA gives UNLIMITED multiplicative homomorphism (no noise growth!).")

Checkpoint 1. RSA multiplication on ciphertexts is exact, no noise accumulates! The catch: textbook RSA is deterministic (same message → same ciphertext), so it's not CPA-secure. More importantly, RSA only supports multiplication, not addition.

2. Paillier: Additively Homomorphic

The Paillier cryptosystem (1999) is additively homomorphic: you can add ciphertexts to get the encryption of the sum. It works in $\mathbb{Z}_{n^2}^*$.

Key generation:

• Choose primes $p, q$. Let $n = pq$, $\lambda = \text{lcm}(p-1, q-1)$

• $g = n + 1$ (standard choice)

• $\mu = \lambda^{-1} \bmod n$

Encrypt: $\text{Enc}(m) = g^m \cdot r^n \bmod n^2$ where $r$ is random

Decrypt: $\text{Dec}(c) = L(c^\lambda \bmod n^2) \cdot \mu \bmod n$ where $L(x) = (x-1)/n$

Homomorphic addition: $\text{Enc}(m_1) \cdot \text{Enc}(m_2) = \text{Enc}(m_1 + m_2) \pmod{n^2}$

# Paillier key generation
p_pail, q_pail = 17, 19
n_pail = p_pail * q_pail  # 323
n2 = n_pail^2  # 104329
lam = lcm(p_pail - 1, q_pail - 1)  # λ = lcm(16, 18) = 144
g = n_pail + 1  # standard generator choice

def L(x, n):
    """L function: (x - 1) / n, integer division."""
    return (x - 1) // n

mu = inverse_mod(L(power_mod(g, lam, n2), n_pail), n_pail)

print(f"=== Paillier Key Generation ===")
print(f"p = {p_pail}, q = {q_pail}")
print(f"n = {n_pail}, n² = {n2}")
print(f"λ = lcm({p_pail-1}, {q_pail-1}) = {lam}")
print(f"g = n + 1 = {g}")
print(f"μ = {mu}")

def paillier_encrypt(m, n, g, n2):
    """Encrypt message m (0 ≤ m < n)."""
    r = randint(1, n - 1)
    while gcd(r, n) != 1:  # r must be coprime to n
        r = randint(1, n - 1)
    c = (power_mod(g, m, n2) * power_mod(r, n, n2)) % n2
    return c

def paillier_decrypt(c, lam, mu, n, n2):
    """Decrypt ciphertext c."""
    x = power_mod(c, lam, n2)
    m = (L(x, n) * mu) % n
    return m

# Encrypt and decrypt
m_test = 42
c_test = paillier_encrypt(m_test, n_pail, g, n2)
d_test = paillier_decrypt(c_test, lam, mu, n_pail, n2)

print(f"Plaintext:  m = {m_test}")
print(f"Ciphertext: c = {c_test}")
print(f"Decrypted:  m = {d_test}")
print(f"Correct? {m_test == d_test}")
print(f"\nNote: ciphertext lives in Z_{n2} (much larger than plaintext space Z_{n_pail})")

# Paillier is probabilistic: same message → different ciphertexts
print("=== Probabilistic Encryption ===")
m_same = 42
for i in range(5):
    c = paillier_encrypt(m_same, n_pail, g, n2)
    print(f"  Enc({m_same}) = {c}")
print(f"\nSame message, different ciphertexts each time!")
print(f"This is essential for CPA security (unlike textbook RSA).")

# Homomorphic addition: multiply ciphertexts!
m1, m2 = 17, 25
c1 = paillier_encrypt(m1, n_pail, g, n2)
c2 = paillier_encrypt(m2, n_pail, g, n2)

# Homomorphic addition = ciphertext multiplication mod n²
c_sum = (c1 * c2) % n2
d_sum = paillier_decrypt(c_sum, lam, mu, n_pail, n2)

print(f"=== Homomorphic Addition ===")
print(f"m1 = {m1}, m2 = {m2}")
print(f"Enc(m1) = {c1}")
print(f"Enc(m2) = {c2}")
print(f"\nEnc(m1) × Enc(m2) mod n² = {c_sum}")
print(f"Dec(result) = {d_sum}")
print(f"m1 + m2 = {m1 + m2}")
print(f"Match? {d_sum == m1 + m2}")
print(f"\nMultiplying Paillier ciphertexts ADDS the plaintexts!")

Checkpoint 2. In Paillier, multiplying two ciphertexts produces the encryption of the sum. This is because $g^{m_1} r_1^n \cdot g^{m_2} r_2^n = g^{m_1+m_2} (r_1 r_2)^n$, the exponents add. Like RSA, there's no noise growth, additions are unlimited.

# Paillier also supports scalar multiplication: Enc(m)^k = Enc(k*m)
m = 7
k = 5
c = paillier_encrypt(m, n_pail, g, n2)

c_scaled = power_mod(c, k, n2)  # Enc(m)^k
d_scaled = paillier_decrypt(c_scaled, lam, mu, n_pail, n2)

print(f"=== Scalar Multiplication ===")
print(f"m = {m}, k = {k}")
print(f"Enc(m)^k mod n² → Dec = {d_scaled}")
print(f"k × m = {k * m}")
print(f"Match? {d_scaled == k * m}")
print(f"\nWith addition + scalar multiplication, Paillier can compute")
print(f"weighted sums, averages, and any LINEAR function on encrypted data.")

# Application: encrypted voting
print("=== Application: Encrypted Voting ===")
print()

# 10 voters, each votes 0 (no) or 1 (yes)
votes = [1, 0, 1, 1, 0, 1, 1, 0, 1, 1]  # secret ballots
print(f"Votes (secret): {votes}")
print(f"True tally: {sum(votes)} yes, {len(votes) - sum(votes)} no")
print()

# Each voter encrypts their vote
encrypted_votes = [paillier_encrypt(v, n_pail, g, n2) for v in votes]
print(f"Encrypted votes: {encrypted_votes[:3]}... (ciphertexts)")

# Tallying authority multiplies all ciphertexts (= adds all votes)
tally_ct = 1
for ev in encrypted_votes:
    tally_ct = (tally_ct * ev) % n2

# Only the key holder can decrypt the tally
tally = paillier_decrypt(tally_ct, lam, mu, n_pail, n2)

print(f"\nEncrypted tally (product of all ciphertexts): {tally_ct}")
print(f"Decrypted tally: {tally} yes votes")
print(f"Correct? {tally == sum(votes)}")
print(f"\nNo one except the key holder learned individual votes!")

3. ElGamal: Multiplicatively Homomorphic

ElGamal encryption is multiplicatively homomorphic, like RSA, but with the advantage of being probabilistic (CPA-secure).

Key generation: Choose group $\mathbb{Z}_p^*$, generator $g$, secret $x$, public $h = g^x$

Encrypt: $\text{Enc}(m) = (g^r, m \cdot h^r)$ for random $r$

Homomorphic multiplication: $(g^{r_1}, m_1 h^{r_1}) \cdot (g^{r_2}, m_2 h^{r_2}) = (g^{r_1+r_2}, m_1 m_2 \cdot h^{r_1+r_2}) = \text{Enc}(m_1 \cdot m_2)$

# ElGamal setup
p_eg = 467  # prime
g_eg = ZZ(GF(p_eg).multiplicative_generator())  # generator
x_eg = randint(2, p_eg - 2)  # secret key
h_eg = power_mod(g_eg, x_eg, p_eg)  # public key

print(f"=== ElGamal Setup ===")
print(f"p = {p_eg}, g = {g_eg}")
print(f"Secret key: x = {x_eg}")
print(f"Public key: h = g^x = {h_eg}")

def elgamal_enc(m, g, h, p):
    r = randint(1, p - 2)
    c1 = power_mod(g, r, p)
    c2 = (m * power_mod(h, r, p)) % p
    return (c1, c2)

def elgamal_dec(ct, x, p):
    c1, c2 = ct
    s = power_mod(c1, x, p)  # shared secret
    m = (c2 * inverse_mod(s, p)) % p
    return m

# Encrypt and verify
m_test = 42
ct_test = elgamal_enc(m_test, g_eg, h_eg, p_eg)
d_test = elgamal_dec(ct_test, x_eg, p_eg)
print(f"\nEnc({m_test}) = {ct_test}")
print(f"Dec = {d_test}")
print(f"Correct? {d_test == m_test}")

# ElGamal homomorphic multiplication
m1, m2 = 7, 11
ct1 = elgamal_enc(m1, g_eg, h_eg, p_eg)
ct2 = elgamal_enc(m2, g_eg, h_eg, p_eg)

# Multiply component-wise
ct_prod = ((ct1[0] * ct2[0]) % p_eg, (ct1[1] * ct2[1]) % p_eg)
d_prod = elgamal_dec(ct_prod, x_eg, p_eg)

print(f"=== ElGamal Homomorphic Multiplication ===")
print(f"m1 = {m1}, m2 = {m2}")
print(f"Dec(Enc(m1) × Enc(m2)) = {d_prod}")
print(f"m1 × m2 mod p = {(m1 * m2) % p_eg}")
print(f"Match? {d_prod == (m1 * m2) % p_eg}")
print(f"\nElGamal is multiplicatively homomorphic AND probabilistic (CPA-secure).")

4. The Limitation: Why Partial Isn't Enough

Scheme	Addition	Multiplication	Noise	CPA-secure
RSA	No	Yes (unlimited)	None	No (deterministic)
Paillier	Yes (unlimited)	No	None	Yes
ElGamal	No	Yes (unlimited)	None	Yes

None of these give us both operations. Why does that matter?

# Why we need BOTH operations: compute a quadratic function
# f(x) = 3x² + 2x + 1
# Needs: multiplication (x*x), scalar multiply (3*x², 2*x), addition

print("=== Why We Need Both Operations ===")
print()
print("Goal: compute f(x) = 3x² + 2x + 1 on encrypted x")
print()
print("With only addition (Paillier):")
print("  ✓ Can compute 2x = x + x")
print("  ✓ Can compute 2x + 1 = Enc(2x) ⊕ Enc(1)")
print("  ✗ Cannot compute x² = x × x")
print()
print("With only multiplication (ElGamal):")
print("  ✓ Can compute x² = x × x")
print("  ✗ Cannot compute 3x² + 2x (needs addition!)")
print()
print("With BOTH (FHE):")
print("  ✓ x² = x ⊗ x")
print("  ✓ 3x² = 3 ⊗ x²")
print("  ✓ 2x = 2 ⊗ x")
print("  ✓ 3x² + 2x + 1 = (3x²) ⊕ (2x) ⊕ 1")
print()
print("Addition + Multiplication = ANY polynomial = ANY arithmetic circuit = ANY computation")

Checkpoint 3. Partial homomorphism is already useful (voting, statistics, auctions), but it can't evaluate arbitrary functions. The key insight for FHE: if you have both addition and multiplication, you can evaluate any arithmetic circuit, and therefore any computation. This is why Gentry's breakthrough was so important.

Crypto foreshadowing. The next notebook introduces BGV, a scheme based on LWE that supports both addition and multiplication, but with noise growth that limits the computation depth. BGV uses modulus switching to manage this noise, avoiding the expensive bootstrapping for many practical circuits.

5. Exercises

Exercise 1 (Worked): Paillier Weighted Sum

Problem. Three employees have salaries $s_1 = 50, s_2 = 75, s_3 = 100$. Compute the average salary using Paillier without revealing individual salaries.

Solution:

# Exercise 1: Worked solution
salaries = [50, 75, 100]
print(f"Salaries (secret): {salaries}")
print(f"True average: {sum(salaries) / len(salaries):.1f}")

# Each employee encrypts their salary
enc_salaries = [paillier_encrypt(s, n_pail, g, n2) for s in salaries]
print(f"\nEncrypted salaries: {enc_salaries}")

# Sum homomorphically
ct_total = 1
for ec in enc_salaries:
    ct_total = (ct_total * ec) % n2

# Decrypt the sum
total = paillier_decrypt(ct_total, lam, mu, n_pail, n2)
average = total / len(salaries)

print(f"\nDecrypted sum: {total}")
print(f"Average: {total}/{len(salaries)} = {average:.1f}")
print(f"Correct? {total == sum(salaries)}")
print(f"\nThe averaging server never saw individual salaries!")

Exercise 2 (Guided): ElGamal Chain

Problem. Encrypt the values 2, 3, 5, 7 with ElGamal. Multiply all four ciphertexts homomorphically and verify the decrypted result equals $2 \times 3 \times 5 \times 7 = 210$.

Fill in the TODOs:

# Exercise 2: fill in the TODOs

# TODO 1: Encrypt each value
# values = [2, 3, 5, 7]
# cts = [elgamal_enc(v, g_eg, h_eg, p_eg) for v in values]

# TODO 2: Multiply all ciphertexts component-wise
# ct_all = cts[0]
# for ct in cts[1:]:
#     ct_all = ((ct_all[0] * ct[0]) % p_eg, (ct_all[1] * ct[1]) % p_eg)

# TODO 3: Decrypt and verify
# result = elgamal_dec(ct_all, x_eg, p_eg)
# expected = 2 * 3 * 5 * 7
# print(f"Decrypted product: {result}")
# print(f"Expected: {expected}")
# print(f"Match? {result == expected % p_eg}")

Exercise 3 (Independent): Paillier Auction

Problem. Design a sealed-bid auction using Paillier:

1. Five bidders submit encrypted bids: 100, 150, 200, 125, 175.

2. The auctioneer computes the encrypted total of all bids.

3. Show that the auctioneer can compute the total but cannot determine individual bids.

4. Challenge: Can Paillier alone determine the highest bid? Why or why not?

# Exercise 3: write your solution here

Summary

Scheme	Homomorphic For	Noise	Key Property
RSA	Multiplication	None	Deterministic, not CPA-secure
Paillier	Addition + scalar multiply	None	Probabilistic, additive group structure in $\mathbb{Z}_{n^2}^*$
ElGamal	Multiplication	None	Probabilistic, multiplicative group structure in $\mathbb{Z}_p^*$
FHE	Both (but with noise)	Grows per operation	Requires noise management (next notebooks)

Partially homomorphic schemes are fast, practical, and noise-free, but they can only compute one type of operation. FHE trades noise-free operation for universality: both addition and multiplication, which is enough to evaluate any circuit.

---

Next: 11c: The BGV Scheme