Homomorphisms

ZK Prereqs Workshop 5 of 6

Structure-preserving maps β€” the mathematical mechanism behind zero knowledge

🌐 The Google Translate of Math

Imagine translating a sentence from English to French, and the meaning stays the same.

That's a homomorphism β€” a translation between mathematical structures where the operations are preserved.

The killer app: What if I could encrypt your computation, run it in encrypted form, and get the right encrypted answer β€” without ever seeing your data?

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

Core Terms We Will Use

Quick refresher before homomorphisms:

  • Binary operation: rule that combines two elements
  • Identity: "do nothing" element (0 for +, 1 for Γ—)
  • Inverse: "undo" element (e.g., 5 + 2 ≑ 0 mod 7)
  • Group: closed + associative + identity + inverses
  • Abelian: order does not matter (a+b = b+a)
  • Cyclic: one element can generate all others
  • Generator: that one starting element (like G on ECs)
Homomorphism = a map that preserves this structure.

What is a Homomorphism?

Given two groups, a homomorphism is a map that keeps the math structure intact.

φ(x \, opA \, y) = φ(x) \, opB \, φ(y)
for all x, y in A

In plain English:

  • Do the operation first, then map
  • OR map first, then do the operation
  • Both paths give the same answer

"op" means operation. In one group it might be +, in the other it might be Γ—.

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!
Path 1: Combine in A, then apply φ
Path 2: Apply φ to each, then combine in B
Result: Same answer either way

Quick Refresher (High-School Math)

We'll use these 4 rules repeatedly:

RuleFormulaExample
Distributivek(a+b)=ka+kb2(3+5)=6+10
Exponent add ruleb^(m+n)=b^m * b^n2^8 = 2^3 * 2^5
Square expansion(a+b)^2 = a^2 + 2ab + b^2(2+3)^2 = 4 + 12 + 9
Mod inverse ideaa * a^-1 ≡ 1 (mod p)3*5 ≡ 1 (mod 7)
If these rules hold, checking homomorphisms becomes mechanical.

Example 1: Integers → Even Integers

Let φ(x) = 2x

  • A = (β„€, +) all integers under addition
  • B = (2β„€, +) even integers under addition
  • φ(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)

A = (strings, concatenation)
B = (β„€≥0, +)
φ(s) = len(s) 
# Ο†(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)

A = (2×2 integer matrices, ×) β€” a Monoid
B = (β„€, ×) β€” a Monoid
φ(M) = det(M) 
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 = ({bi : i ∈ β„€}, ×)

φ(x) = bx

φ(a + b) = ba+b = ba × bb = φ(a) × φ(b) 
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}")
Addition on one side becomes multiplication on the other.
This is the basis of how elliptic curve scalar multiplication works!

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
The trivial homomorphism: φ(a) = eB for all a.
It's valid (φ(aβ–‘b) = e = e β–  e = φ(a)β– φ(b)) but tells us nothing useful.

⚑ Spot the Homomorphism

Vote YES or NO for each β€” is it a valid homomorphism?

MapVerdict
Ο†(x) = 2x from (β„€,+) to (β„€,+)YES β€” 2(a+b) = 2a+2b βœ“
Ο†(x) = xΒ² from (β„€,+) to (β„€,+)NO β€” (a+b)Β² β‰  aΒ²+bΒ²
Ο†(x) = x+1 from (β„€,+) to (β„€,+)NO β€” (a+b)+1 β‰  (a+1)+(b+1)
det(AB) vs det(A)Β·det(B)YES β€” determinant is a homomorphism!
Ο†(x) = eΛ£ from (ℝ,+) to (ℝ⁺,Γ—)YES β€” e^(a+b) = eᡃ Γ— eᡇ βœ“

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

If φ is computationally difficult to invert,
then φ homomorphically encrypts the elements of A.
  • φ 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 matches 15 (mod group order) βœ“

# 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
"Multiplication by a constant" is really repeated addition.
Repeated addition = scalar multiplication on the curve.

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
EC points give us a one-way homomorphism:
Easy: integer → EC point (compute xG)
Hard: EC point → integer (discrete log)

The Big Picture

"Elliptic curve points in a finite field under addition are a finite cyclic group, and integers under addition are homomorphic to this group."

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!
The same φ works for both additive and multiplicative homomorphisms.
This is because finite fields have both group structures.

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
You now have the complete mathematical foundation for understanding ZK proofs!

Practice Problems

  1. Verify that φ(x) = 3x is a homomorphism from (β„€, +) to ({3i}, ×) 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) = x2 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.