FHE toy implementations

2025-07-14   fhe programming sketch

---

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

#!/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("<span class="has-background-warning">= Somewhat Homomorphic Encryption Demo </span>=\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<span class="has-background-warning">= Computing (a AND b) XOR c on encrypted data </span>=")
    
    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<span class="has-background-warning">= Key Insights </span>=")
    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...

1. Basic Encryption/Decryption:
   

   0 -> 73672351051154827076988436655639907227796466639059429097242021101333242850930414192304 -> 0 ✓
   

   1 -> 129699300680728142812942519098478978480876554303056246340664324398447157539237363979042 -> 1 ✓
   

2. Homomorphic Addition (XOR):
   

   0 ⊕ 0 = 0, decrypted: 0 ✓
   

   0 ⊕ 1 = 1, decrypted: 1 ✓
   

   1 ⊕ 0 = 1, decrypted: 1 ✓
   

   1 ⊕ 1 = 0, decrypted: 0 ✓
   

3. Homomorphic Multiplication (AND):
   

   0 ∧ 0 = 0, decrypted: 0 ✓
   

   0 ∧ 1 = 0, decrypted: 0 ✓
   

   1 ∧ 0 = 0, decrypted: 0 ✓
   

   1 ∧ 1 = 1, decrypted: 1 ✓
   

4. 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)

```py
n = 512<br>

q = 3329<br>

noise_distribution = [-3, 3]<br>

<br>

def get_LWE_sample(s):<br>

    A = random_matrix(n, n)<br>

    e = random_noise_vector(n)<br>

    b = A * s + e<br>

    return (A, b)<br>

<br>

def keygen():<br>

    s = random_vector(n)<br>

    return s<br>

<br>

def encrypt(s, x):<br>

    assert x <span class="has-background-warning"> 0 or x </span> 1<br>

    (A, b) = get_LWE_sample(s)<br>

    c = b + floor(q / 2) * x<br>

    return (A, c)<br>

<br>

def decrypt(s, (A, c)):<br>

    raw = c - A * s<br>

    return round(raw * 2 / q)<br>

Private Information Retrieval (with above methods)

n = 512<br>

q = 3329<br>

noise_distribution = [-3, 3]<br>

<br>

num_items_in_db = 50<br>

desired_idx = 24<br>

db = [random_bit() for i in range(num_items_in_db)]<br>

<br>

def generate_query(desired_idx):<br>

    v = []<br>

    for i in range(num_items_in_db):<br>

        bit = 1 if i == desired_idx else 0<br>

        ct = encrypt(s, bit)<br>

        v.append(ct)<br>

    return v<br>

<br>

def answer_query(query, db):<br>

    summed_A = zero_matrix(n, n)<br>

    summed_c = zero_vector(n)<br>

    for i in range(num_items_in_db):<br>

        if db[i] == 1:<br>

            (A, c) = query[i]<br>

            summed_A += A<br>

            summed_c += c<br>

    return (summed_A, summed_c)<br>

<br>

s = keygen()<br>

query = generate_query(desired_idx)<br>

<br>

print("Sending the query to the server...")<br>

<br>

answer = answer_query(query, db)<br>

<br>

print("Got the answer back from the server...")<br>

<br>

result = decrypt(s, answer)<br>

<br>

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

<br>

assert result == db[desired_idx]<br>

print("PIR was correct!")<br>

Bit-wise Fully Homomorphic Encryption

https://chatgpt.com/share/6876953d-5f9c-8010-b9ca-aaee29424ad7

Encrypting a bit (conceptual)

b ∈ {0,1} -> the message bit to be encrypted m -> the number of rows in matrix A r ∈ {0,1}^m -> random binary sparse vector

Computation:

1. Generate a random sparse binary vector:<br>

<br>

   r ∈ {0, 1}^m  with Hamming weight  k ≪ m<br>

<br>

2. Compute ciphertext components:<br>

<br>

   c1 = rᵗ · A             ∈ ℤ_q^n<br>

   c2 = rᵗ · b + (q//2) · b   ∈ ℤ_q<br>

<br>

3. Final ciphertext:<br>

<br>

   (c1, c2)<br>

We choose a random sparse vector r ∈ {0,1}^m

Fully HE Implementations

See https://github.com/vbuterin/research/blob/master/tensor_fhe/homomorphic_encryption.py

• explained by Vitalik in Exploring Fully Homomorphic Encryption by Vitalik and https://www.youtube.com/watch?v=sSSRkzvI2Sk

CKKS build from scratch series at CKKS explained Part 1, Vanilla Encoding and Decoding

Other

• Building Safe AI - A Tutorial for Encrypted Deep Learning - i am trask

---

---

---