Homomorphisms

ZK Prereqs Workshop 5 of 6

Structure-preserving maps — the mathematical mechanism behind zero knowledge

Agenda

• What is a homomorphism?
• Simple examples: integers, strings, matrices
• Clarifications & common misconceptions
• The exponentiation homomorphism
• Rational numbers → finite fields
• Homomorphic encryption
• Zero knowledge proofs via homomorphisms

What is a Homomorphism?

Given two groups (A, □) and (B, ■), a homomorphism from A to B is a function φ such that:

In plain English:

• Combine in A first, then map → same result as
• Map each element first, then combine in B

The map "preserves" the group structure — operations in A correspond to operations in B.

Homomorphism Visualized

   Group A (□)              Group B (■)
   ─────────               ─────────
   a_i ──────── φ ────────→ φ(a_i)
    □                          ■
   a_j ──────── φ ────────→ φ(a_j)
    ↓                          ↓
   a_i □ a_j                φ(a_i) ■ φ(a_j)
    │                          │
    └────── φ ────────→  φ(a_i □ a_j)
    
    Both paths give the SAME result!

Example 1: Integers → Even Integers

Let φ(x) = 2x

# Verify:
# φ(a + b) = φ(a) + φ(b)
# 2(a + b) = 2a + 2b  ✓

a, b = 3, 5
lhs = 2 * (a + b)  # = 16
rhs = 2*a + 2*b    # = 16
assert lhs == rhs

print(f"φ({a}+{b}) = φ({a+b}) = {lhs}")
print(f"φ({a})+φ({b}) = {2*a}+{2*b} = {rhs}")
# Both equal 16 ✓

Example 2: Strings → Integers

Let φ = length function (len)

# φ(concat(s1, s2)) = φ(s1) + φ(s2)
# len("Rare" + "Skills") = len("Rare") + len("Skills")

s1, s2 = "Rare", "Skills"
lhs = len(s1 + s2)           # len("RareSkills") = 10
rhs = len(s1) + len(s2)      # 4 + 6 = 10
assert lhs == rhs

print(f"len('{s1}' + '{s2}') = len('{s1+s2}') = {lhs}")
print(f"len('{s1}') + len('{s2}') = {len(s1)} + {len(s2)} = {rhs}")
# Both equal 10 ✓

The string length is a homomorphism from strings under concatenation to non-negative integers under addition.

Example 3: Matrices → Integers (Determinant)

Let φ = det (determinant)

import numpy as np

A = np.array([[1, 2], [3, 4]])
B = np.array([[5, 6], [7, 8]])
C = A @ B  # matrix multiplication

det_A = int(round(np.linalg.det(A)))  # -2
det_B = int(round(np.linalg.det(B)))  # -2
det_C = int(round(np.linalg.det(C)))  # 4

print(f"det(A×B) = {det_C}")
print(f"det(A) × det(B) = {det_A} × {det_B} = {det_A * det_B}")
assert det_C == det_A * det_B  # 4 = (-2)×(-2) ✓

The Exponentiation Homomorphism

A = (ℤ, +)  →  B = ({bⁱ : i ∈ ℤ}, ×)

base = 2

# φ(a + b) = φ(a) × φ(b)
a, b = 3, 5
lhs = base ** (a + b)        # 2^8 = 256
rhs = base**a * base**b      # 8 × 32 = 256
assert lhs == rhs

# Addition in integers maps to multiplication in powers!
print(f"2^({a}+{b}) = 2^{a+b} = {lhs}")
print(f"2^{a} × 2^{b} = {base**a} × {base**b} = {rhs}")

Important Clarifications

• One-directional: φ maps A → B, but there's no requirement for B → A
• Not always exists: arbitrary groups may have no homomorphism between them
• Not necessarily bijective: φ doesn't need to hit every element of B
• Trivial homomorphism: mapping everything to the identity always works (but is useless)
• Multiple homomorphisms: there can be more than one φ between A and B

Rationals → Finite Field

φ(a/b) = a × b^-1 (mod p)

p = 17

def phi(num, den):
    return (num * pow(den, -1, p)) % p

# 1/3 + 3/5 = 14/15 in regular math
a = phi(1, 3)   # φ(1/3) 
b = phi(3, 5)   # φ(3/5)
c = phi(14, 15) # φ(14/15)

print(f"φ(1/3) = {a}")    # 6
print(f"φ(3/5) = {b}")    # 4
print(f"φ(14/15) = {c}")  # 10

# Check: φ(1/3) + φ(3/5) ≡ φ(14/15) (mod 17)?
print(f"φ(1/3) + φ(3/5) = {(a + b) % p}")  # 10
assert (a + b) % p == c  # ✓ Homomorphism preserved!

Homomorphic Encryption

• φ maps from "secret space" A to "public space" B
• We can verify computations in B without knowing values in A
• Because φ preserves structure, computations in B reflect computations in A
• Because φ is hard to invert, nobody can recover the original values

This is the fundamental mechanism of zero knowledge proofs!

Zero Knowledge Proof: Addition

Claim: "I know two numbers x and y such that x + y = 15"

# Setup: φ maps integers to elliptic curve points
# φ(x) = x × G  (scalar multiplication by generator)
# This is hard to invert (discrete logarithm problem)

# Prover sends:
#   A = φ(x) = xG
#   B = φ(y) = yG
#   claim: x + y = 15

# Verifier checks:
#   A ■ B  ==?  φ(15)
#   xG + yG ==? 15G
#
# By the homomorphism property:
#   φ(x + y) = φ(x) + φ(y) = xG + yG
#
# If xG + yG = 15G, then x + y = 15 ✓

# The verifier is convinced WITHOUT knowing x or y!

Zero Knowledge Proof: Scalar Multiplication

Claim: "I know a and b, and b = 5a"

# Prover sends: φ(a) and φ(b)
# i.e., aG and bG

# Verifier checks:
#   φ(a) + φ(a) + φ(a) + φ(a) + φ(a) ==? φ(b)
#   5 × (aG) ==? bG
#
# Remember: "5 × (aG)" is repeated ADDITION
# That's just 5aG

# If 5(aG) = bG, then 5a = b ✓

# Pseudocode:
# A = multiply(G1, a)     # prover computes aG
# B = multiply(G1, b)     # prover computes bG
# assert multiply(A, 5) == B  # verifier checks 5(aG) = bG

Why Elliptic Curve Points?

What makes EC points perfect for φ?

• Group structure: EC points form a finite cyclic abelian group
• Homomorphism: φ(x) = xG preserves addition
• Hard to invert: given xG, finding x is the discrete logarithm problem
• Efficient: point addition and scalar multiplication are fast
• Compact: points can be represented with ~256 bits

The Big Picture

You now understand every word of this sentence:

1. EC points under addition: closed, associative, has identity, has inverses
2. Finite cyclic: bounded number of elements, all generated from G
3. Integers under addition: the familiar group we know
4. Homomorphic: φ(a+b) = φ(a) + φ(b), i.e., (a+b)G = aG + bG

This one sentence encodes EVERYTHING you need to know about how ZK proofs work at a high level.

Demo: Homomorphism in Action

# Verify the homomorphism property in Python
# φ(a + b) = φ(a) + φ(b) where φ(x) = 2^x

base = 2

# Test with many pairs
import random
for _ in range(5):
    a = random.randint(1, 20)
    b = random.randint(1, 20)
    
    # Path 1: add then map
    path1 = base ** (a + b)
    
    # Path 2: map then multiply
    path2 = (base ** a) * (base ** b)
    
    assert path1 == path2
    print(f"a={a:2d}, b={b:2d}: "
          f"{base}^({a}+{b})={path1}, "
          f"{base}^{a}×{base}^{b}={path2} ✓")

Advanced: Rationals → Finite Field (Multiplicative)

p = 17

def phi(num, den):
    return (num * pow(den, -1, p)) % p

# Multiplicative homomorphism:
# φ(1/3 × 3/5) = φ(1/3) × φ(3/5)

# 1/3 × 3/5 = 1/5 in regular math
a = phi(1, 3)    # φ(1/3) = 6
b = phi(3, 5)    # φ(3/5) = 4  
c = phi(1, 5)    # φ(1/5) = 7

print(f"φ(1/3) × φ(3/5) = {a} × {b} = {(a*b) % p}")  # 24 mod 17 = 7
print(f"φ(1/5) = {c}")  # 7
assert (a * b) % p == c  # ✓ Works for multiplication too!

Key Takeaways

• Homomorphism: φ(a □ b) = φ(a) ■ φ(b) — structure-preserving map
• One-directional: A → B, not necessarily B → A
• Homomorphic encryption: if φ is hard to invert, it encrypts values
• ZK proofs: prover maps secrets to EC space, verifier checks there
• (a+b)G = aG + bG — the core identity of elliptic curve ZK
• The discrete logarithm problem makes φ(x) = xG a one-way function

Practice Problems

1. Verify that φ(x) = 3^x is a homomorphism from (ℤ, +) to ({3ⁱ}, ×) for 5 random pairs.
2. Define φ from real numbers to n×m matrices. Hint: fill every entry with the same number.
3. Find a homomorphism from polynomials with real coefficients to real numbers. Hint: what operation reduces a polynomial to a single number?
4. Why is φ(x) = x² NOT a homomorphism from (ℤ, +) to (ℤ, +)?
5. Given φ(1/3) = 6 and φ(3/5) = 4 in GF(17), compute φ(1/3 + 3/5) and verify by computing φ(14/15) directly.

Next Workshop

Elliptic Curve Cryptography

• Elliptic curve geometry & point addition
• Elliptic curves over finite fields
• The bn128 curve (Ethereum)
• Scalar multiplication & the discrete log problem
• Building a basic ZK proof with py_ecc

The final workshop — where all prerequisites converge into actual ZK cryptography.