FHE toy implementations | Barış Özmen

Partial HE (Paillier) - additive homomorphism

import sympy, random

def generate_keypair(bit_length=512):
    p = sympy.nextprime(random.getrandbits(bit_length))
    q = sympy.nextprime(random.getrandbits(bit_length))
    n = p * q
    g = n + 1
    lambda_ = (p - 1) * (q - 1)
    mu = sympy.mod_inverse(lambda_, n)
    return (n, g), (lambda_, mu)

def encrypt(m, public_key):
    n, g = public_key
    r = random.randint(1, n - 1)
    return (pow(g, m, n**2) * pow(r, n, n**2)) % (n**2)

def decrypt(c, private_key, public_key):
    lambda_, mu = private_key
    n, _ = public_key
    l = (pow(c, lambda_, n**2) - 1) // n
    return (l * mu) % n

def homomorphic_sum(a, b, public_key):
    return (a * b) % (public_key[0]**2)


public_key, private_key = generate_keypair(128)

enc1 = encrypt(5, public_key)
print(enc1) # 75042696080311881003721105285833023546234037256871189406054603593273414107194675808782154359890875636008219678257354647151456750847402457204123856890

enc2 = encrypt(3, public_key)
print(enc2) # 269297253929306291153284608946414491483346738328838888044406160105950588673820650688249910373352597049965491330298818622410901670587359945691000319758

enc_sum = homomorphic_sum(enc1, enc2, public_key)
print(enc_sum) # 232817745404365921249916946617154013580946738803385878188677616867767489473531493655408124901849935882016399498283109322848069064027287561237823608127

dec_sum = decrypt(enc_sum, private_key, public_key)
print(dec_sum) # 8

Here is the colab notebook link for you to run and play with yourself. I highly recommend. It will give valuable intuition Note that ciphertexts will be different at each run, as encryption process is non-deterministic (notice the random methods). Above commented print outputs are from a single run, for showing how a ciphertext looks like under Paillier.

Somewhat HE Implementation

Inspired from the example in Exploring Fully Homomorphic Encryption by Vitalik (archived)

#!/usr/bin/env python3
"""
Somewhat Homomorphic Encryption Implementation
Based on the approximate GCD problem - Craig Gentry's foundational approach.

This implementation demonstrates the core principles of homomorphic encryption:
- Encrypt bits (0 or 1) where addition becomes XOR
- Support homomorphic addition and multiplication
- Limited multiplicative depth due to noise growth

Author: In the style of Peter Norvig (elegant code) and Vitalik Buterin (crypto insight)
"""

import random
import secrets
from typing import Tuple, List
from dataclasses import dataclass


@dataclass
class SomewhatHEParams:
    """Parameters for the somewhat-HE scheme"""
    lambda_: int  # Security parameter (key size in bits)
    rho: int      # Noise parameter (noise size in bits)  
    eta: int      # Error parameter (error size in bits)

    @classmethod
    def default(cls) -> 'SomewhatHEParams':
        """Conservative parameters for demonstration"""
        return cls(lambda_=128, rho=32, eta=8)


class SomewhatHE:
    """
    Somewhat Homomorphic Encryption based on approximate GCD

    Key insight: Security relies on the difficulty of finding GCD 
    when numbers are only approximate multiples of the secret key.
    """

    def __init__(self, params: SomewhatHEParams = None):
        self.params = params or SomewhatHEParams.default()
        self.secret_key = self._generate_secret_key()

    def _generate_secret_key(self) -> int:
        """Generate a large odd prime as the secret key"""
        # For demonstration, we'll use a large odd number
        # In practice, you'd want a prime, but odd suffices for the concept
        key = secrets.randbits(self.params.lambda_)
        return key | 1  # Ensure it's odd

    def encrypt(self, bit: int) -> int:
        """
        Encrypt a single bit (0 or 1)

        Formula: c = m + 2*r + q*p
        where:
        - m is the message bit (0 or 1)
        - r is small random noise
        - q is large random value
        - p is the secret key
        """
        if bit not in [0, 1]:
            raise ValueError("Can only encrypt bits (0 or 1)")

        # Generate large random multiplier q
        q = secrets.randbits(self.params.lambda_ + self.params.rho)

        # Generate small random noise r
        r = secrets.randbits(self.params.eta)

        # Compute ciphertext: c = m + 2*r + q*p
        ciphertext = bit + 2 * r + q * self.secret_key

        return ciphertext

    def decrypt(self, ciphertext: int) -> int:
        """
        Decrypt a ciphertext back to a bit

        Formula: m = (c mod p) mod 2
        """
        # First mod p removes the q*p term
        # Second mod 2 removes the 2*r term (since r is small)
        return (ciphertext % self.secret_key) % 2

    def add(self, c1: int, c2: int) -> int:
        """
        Homomorphic addition (XOR for bits)

        Addition of ciphertexts corresponds to XOR of plaintexts
        """
        return c1 + c2

    def multiply(self, c1: int, c2: int) -> int:
        """
        Homomorphic multiplication (AND for bits)

        Multiplication of ciphertexts corresponds to AND of plaintexts
        WARNING: Each multiplication roughly doubles noise and ciphertext size
        """
        return c1 * c2

    def get_noise_estimate(self, ciphertext: int) -> int:
        """
        Estimate the noise level in a ciphertext
        Higher noise means fewer operations possible before decryption fails
        """
        reduced = ciphertext % self.secret_key
        return min(reduced, self.secret_key - reduced)


def demonstrate_homomorphic_properties():
    """Demonstrate the homomorphic properties with clear examples"""
    print("<mark>= Somewhat Homomorphic Encryption Demo </mark>=\n")

    # Initialize the scheme
    he = SomewhatHE()
    print(f"Secret key size: {he.secret_key.bit_length()} bits")
    print(f"Secret key (first 20 chars): {str(he.secret_key)[:20]}...\n")

    # Test basic encryption/decryption
    print("1. Basic Encryption/Decryption:")
    for bit in [0, 1]:
        encrypted = he.encrypt(bit)
        decrypted = he.decrypt(encrypted)
        print(f"   {bit} -> {encrypted} -> {decrypted} ✓")

    print("\n2. Homomorphic Addition (XOR):")
    test_cases = [(0, 0), (0, 1), (1, 0), (1, 1)]

    for a, b in test_cases:
        enc_a = he.encrypt(a)
        enc_b = he.encrypt(b)
        enc_sum = he.add(enc_a, enc_b)
        dec_sum = he.decrypt(enc_sum)
        expected = a ^ b  # XOR for binary addition

        status = "✓" if dec_sum == expected else "✗"
        print(f"   {a} ⊕ {b} = {expected}, decrypted: {dec_sum} {status}")

    print("\n3. Homomorphic Multiplication (AND):")
    for a, b in test_cases:
        enc_a = he.encrypt(a)
        enc_b = he.encrypt(b)
        enc_product = he.multiply(enc_a, enc_b)
        dec_product = he.decrypt(enc_product)
        expected = a & b  # AND for binary multiplication

        status = "✓" if dec_product == expected else "✗"
        print(f"   {a} ∧ {b} = {expected}, decrypted: {dec_product} {status}")

    print("\n4. Noise Growth Demonstration:")
    enc_1 = he.encrypt(1)
    current = enc_1

    print(f"   Initial noise: ~{he.get_noise_estimate(current)} bits")

    for i in range(3):
        current = he.multiply(current, enc_1)  # Multiply by 1 (should stay 1)
        decrypted = he.decrypt(current)
        noise = he.get_noise_estimate(current)

        print(f"   After {i+1} multiplication(s): decrypted={decrypted}, noise=~{noise} bits")

        if decrypted != 1:
            print(f"   ⚠️  Decryption failed after {i+1} multiplications!")
            break


def compute_encrypted_circuit():
    """Demonstrate computing a simple circuit on encrypted data"""
    print("\n<mark>= Computing (a AND b) XOR c on encrypted data </mark>=")

    he = SomewhatHE()

    # Input values
    a, b, c = 1, 0, 1
    print(f"Plaintext inputs: a={a}, b={b}, c={c}")

    # Encrypt inputs
    enc_a = he.encrypt(a)
    enc_b = he.encrypt(b)
    enc_c = he.encrypt(c)

    # Compute (a AND b) XOR c homomorphically
    enc_and = he.multiply(enc_a, enc_b)  # a AND b
    enc_result = he.add(enc_and, enc_c)   # (a AND b) XOR c

    # Decrypt result
    result = he.decrypt(enc_result)
    expected = (a & b) ^ c

    print(f"Expected result: ({a} ∧ {b}) ⊕ {c} = {expected}")
    print(f"Homomorphic result: {result}")
    print(f"Circuit evaluation: {'✓' if result == expected else '✗'}")


if __name__ == "__main__":
    # Set random seed for reproducible demos
    random.seed(42)

    demonstrate_homomorphic_properties()
    compute_encrypted_circuit()

    print("\n<mark>= Key Insights </mark>=")
    print("• Homomorphic encryption allows computation on encrypted data")
    print("• Addition of ciphertexts = XOR of plaintexts")
    print("• Multiplication of ciphertexts = AND of plaintexts")
    print("• Noise grows with each operation, limiting circuit depth")
    print("• Security based on approximate GCD problem")
    print("• This is 'somewhat' HE - limited multiplications before noise overwhelms")

= Somewhat Homomorphic Encryption Demo =

Secret key size: 127 bits Secret key (first 20 chars): 14672464141087887555...

Basic Encryption/Decryption: 0 -> 73672351051154827076988436655639907227796466639059429097242021101333242850930414192304 -> 0 ✓ 1 -> 129699300680728142812942519098478978480876554303056246340664324398447157539237363979042 -> 1 ✓
Homomorphic Addition (XOR): 0 ⊕ 0 = 0, decrypted: 0 ✓ 0 ⊕ 1 = 1, decrypted: 1 ✓ 1 ⊕ 0 = 1, decrypted: 1 ✓ 1 ⊕ 1 = 0, decrypted: 0 ✓
Homomorphic Multiplication (AND): 0 ∧ 0 = 0, decrypted: 0 ✓ 0 ∧ 1 = 0, decrypted: 0 ✓ 1 ∧ 0 = 0, decrypted: 0 ✓ 1 ∧ 1 = 1, decrypted: 1 ✓
Noise Growth Demonstration: Initial noise: ~401 bits After 1 multiplication(s): decrypted=1, noise=~160801 bits After 2 multiplication(s): decrypted=1, noise=~64481201 bits After 3 multiplication(s): decrypted=1, noise=~25856961601 bits

= Computing (a AND b) XOR c on encrypted data = Plaintext inputs: a=1, b=0, c=1 Expected result: (1 ∧ 0) ⊕ 1 = 1 Homomorphic result: 1 Circuit evaluation: ✓

= Key Insights = • Homomorphic encryption allows computation on encrypted data • Addition of ciphertexts = XOR of plaintexts • Multiplication of ciphertexts = AND of plaintexts • Noise grows with each operation, limiting circuit depth • Security based on approximate GCD problem • This is 'somewhat' HE - limited multiplications before noise overwhelms

Somewhat HE's Mathematical Proofs of Homomorphic Encryption Properties

Demonstrating why the somewhat-HE scheme works algebraically

In the style of Peter Norvig (elegant proofs) and Vitalik Buterin (crypto rigor)

Proof of Additive Homomorphism

Theorem: Addition of ciphertexts corresponds to XOR of plaintexts.

Given

Two ciphertexts: - c₁ = m₁ + 2r₁ + q₁p - c₂ = m₂ + 2r₂ + q₂p

Proof

Their sum is: c₁ + c₂ = (m₁ + 2r₁ + q₁p) + (m₂ + 2r₂ + q₂p) = (m₁ + m₂) + 2(r₁ + r₂) + (q₁ + q₂)p

This has the exact same form as a fresh ciphertext: c_sum = m_sum + 2r_sum + q_sum·p

where: - m_sum = m₁ + m₂ (mod 2) = m₁ ⊕ m₂ - r_sum = r₁ + r₂ - q_sum = q₁ + q₂

Decryption

decrypt(c₁ + c₂) = ((c₁ + c₂) mod p) mod 2
                 = ((m₁ + m₂) + 2(r₁ + r₂)) mod 2
                 = (m₁ + m₂) mod 2
                 = m₁ ⊕ m₂

∴ Addition of ciphertexts = XOR of plaintexts ✓

Proof of Multiplicative Homomorphism

Theorem: Multiplication of ciphertexts corresponds to AND of plaintexts.

Given

Two ciphertexts: - c₁ = m₁ + 2r₁ + q₁p - c₂ = m₂ + 2r₂ + q₂p

Proof

Their product is: c₁ · c₂ = (m₁ + 2r₁ + q₁p)(m₂ + 2r₂ + q₂p)

Expanding (FOIL method): = m₁m₂ + m₁(2r₂) + m₁(q₂p) + (2r₁)m₂ + (2r₁)(2r₂) + (2r₁)(q₂p) + (q₁p)m₂ + (q₁p)(2r₂) + (q₁p)(q₂p)

Grouping terms: = m₁m₂ + 2(m₁r₂ + r₁m₂ + 2r₁r₂) + p(m₁q₂ + q₁m₂ + 2r₁q₂ + q₁q₂p)

This has the form: m_new + 2r_new + q_new·p

where: - m_new = m₁m₂ = m₁ ∧ m₂ (for bits) - r_new = m₁r₂ + r₁m₂ + 2r₁r₂ - q_new = m₁q₂ + q₁m₂ + 2r₁q₂ + q₁q₂p

Decryption

decrypt(c₁ · c₂) = ((c₁ · c₂) mod p) mod 2
                 = (m₁m₂ + 2r_new) mod 2
                 = m₁m₂ mod 2
                 = m₁ ∧ m₂

∴ Multiplication of ciphertexts = AND of plaintexts ✓

Noise Growth Analysis

Initial Conditions

Initial ciphertext noise: |r| ≈ 2^η bits

After Addition

New noise: r₁ + r₂
Size: |r₁ + r₂| ≤ |r₁| + |r₂| ≈ 2·2^η
Growth: Linear

After Multiplication

New noise: m₁r₂ + r₁m₂ + 2r₁r₂
Since m₁, m₂ ∈ {0,1}, worst case when both = 1:
|r_new| ≤ |r₁| + |r₂| + 2|r₁||r₂|
≈ 2^η + 2^η + 2·2^η·2^η = 2·2^η + 2^(2η+1)
Growth: Quadratic!

Circuit Depth Limitation

Noise must stay < p/2 for correct decryption
Each multiplication roughly doubles noise
Max depth ≈ log₂(p/2^η) multiplications
This is why it's 'somewhat' homomorphic

Key Insight

Noise growth is the fundamental barrier to fully homomorphic encryption.

Gentry's breakthrough was 'bootstrapping' - refreshing ciphertexts to reduce noise.

Security: Approximate vs Exact GCD

Exact GCD Problem (EASY)

Given: x₁ = q₁p, x₂ = q₂p, x₃ = q₃p, ...

Find: p = gcd(x₁, x₂, x₃, ...)

Solution: Euclidean algorithm - O(log n) time

Approximate GCD Problem (HARD)

Given: x₁ = q₁p + r₁, x₂ = q₂p + r₂, x₃ = q₃p + r₃, ...

Find: p

Where: |rᵢ| << p (small noise)

Why It's Hard

Noise 'hides' the exact multiples of p
Standard GCD algorithms fail
Best known attacks are exponential in security parameter
Security assumption: approximate GCD is intractable

Critical Insight

This is why we need the 2r noise term - without it, the scheme would be trivially breakable!

Summary

Mathematical Foundations

Homomorphic properties follow from algebraic structure
Addition preserves ciphertext form → additive homomorphism
Multiplication preserves ciphertext form → multiplicative homomorphism
Noise grows quadratically with multiplication → limited depth
Security relies on approximate GCD hardness assumption

Historical Impact

This framework led to Gentry's FHE breakthrough in 2009

The somewhat-HE scheme demonstrates the core principles that made fully homomorphic encryption possible: 1. Algebraic structure enables homomorphic operations 2. Noise management is the key technical challenge 3. Bootstrapping (evaluating decryption homomorphically) solves the noise problem 4. Approximate problems provide cryptographic security

"The beauty of homomorphic encryption lies not in its complexity, but in the elegant algebraic structure that makes computation on encrypted data possible."

— Peter Norvig meets Vitalik Buterin

Regev's Scheme

From Private information retrieval using homomorphic encryption (explained from scratch) (archived) pythonpy n = 512 q = 3329 noise_distribution = [-3, 3]

def getLWEsample(s): A = randommatrix(n, n) e = randomnoise_vector(n) b = A * s + e return (A, b)

def keygen(): s = random_vector(n) return s

def encrypt(s, x): assert x 0 or x 1 (A, b) = getLWEsample(s) c = b + floor(q / 2) * x return (A, c)

def decrypt(s, (A, c)): raw = c - A * s return round(raw * 2 / q) ```

Private Information Retrieval (with above methods) ```python n = 512 q = 3329 noise_distribution = [-3, 3]

numitemsindb = 50 desiredidx = 24 db = [randombit() for i in range(numitemsindb)]

def generatequery(desiredidx): v = [] for i in range(numitemsindb): bit = 1 if i == desiredidx else 0 ct = encrypt(s, bit) v.append(ct) return v

def answerquery(query, db): summedA = zeromatrix(n, n) summedc = zerovector(n) for i in range(numitemsindb): if db[i] == 1: (A, c) = query[i] summedA += A summedc += c return (summedA, summedc)

s = keygen() query = generatequery(desiredidx)

print("Sending the query to the server...")

answer = answer_query(query, db)

print("Got the answer back from the server...")

result = decrypt(s, answer)

print("The item at index %d of the database is %d", desired_idx, result)

assert result == db[desired_idx] print("PIR was correct!") ```