seal-google-fhe.ipynb

Kernel: SageMath 10.0

Connect: Microsoft SEAL and Google FHE Compiler

Module 11 | Real-World Connections

FHE has moved from theory to production libraries. We survey the ecosystem and show how Module 11's math maps to real API calls.

Introduction

In Module 11 we built toy FHE schemes from scratch: Paillier, BGV-like, BFV-like, and CKKS-like constructions. Production FHE requires much more engineering:

• Number Theoretic Transforms (NTT) for fast polynomial multiplication

• Relinearization to keep ciphertext size manageable after multiplication

• Modulus switching and rescaling for noise management

• Batching (SIMD) to encrypt and process many values at once

Several production-quality libraries handle all of this. In this notebook, we survey the major ones and show how Module 11's concepts map to their APIs.

The Major FHE Libraries

Library	Maintainer	Schemes	Language	License
Microsoft SEAL	Microsoft Research	BFV, CKKS	C++ (Python/C# wrappers)	MIT
OpenFHE	Duality Technologies / DARPA	BGV, BFV, CKKS, TFHE	C++ (Python wrapper)	BSD
HElib	IBM Research	BGV, CKKS	C++	Apache 2.0
TFHE	Zama	TFHE (gate bootstrapping)	C/C++/Rust	Apache 2.0
Concrete	Zama	TFHE-based	Rust/Python	BSD
Lattigo	EPFL/Tune Insight	BGV, BFV, CKKS	Go	Apache 2.0

Plus compilers that transpile high-level code to FHE circuits:

• Google FHE Compiler: C++ to FHE circuits via TFHE

• Concrete ML (Zama): scikit-learn/PyTorch models to FHE

• EVA (Microsoft): optimizing compiler for CKKS programs

# How Module 11 concepts map to SEAL API calls (pseudocode)
print('=== Module 11 Concepts --> Microsoft SEAL API ===')
print()

seal_mapping = [
    ('Choose parameters (n, q, t)',
     'EncryptionParameters parms(scheme_type::bfv);\n'
     '     parms.set_poly_modulus_degree(4096);\n'
     '     parms.set_coeff_modulus(CoeffModulus::BFVDefault(4096));\n'
     '     parms.set_plain_modulus(256);'),
    ('Key generation',
     'KeyGenerator keygen(context);\n'
     '     SecretKey sk = keygen.secret_key();\n'
     '     PublicKey pk; keygen.create_public_key(pk);'),
    ('Encrypt a plaintext',
     'Plaintext pt("42");\n'
     '     Ciphertext ct;\n'
     '     encryptor.encrypt(pt, ct);'),
    ('Homomorphic addition',
     'evaluator.add(ct1, ct2, ct_sum);'),
    ('Homomorphic multiplication',
     'evaluator.multiply(ct1, ct2, ct_prod);\n'
     '     evaluator.relinearize_inplace(ct_prod, relin_keys);'),
    ('Decrypt the result',
     'Plaintext result;\n'
     '     decryptor.decrypt(ct_result, result);'),
    ('Check noise budget',
     'int budget = decryptor.invariant_noise_budget(ct);\n'
     '     // Returns bits of noise budget remaining'),
]

for concept, api in seal_mapping:
    print(f'Module 11: {concept}')
    print(f'  SEAL:    {api}')
    print()

Microsoft SEAL: BFV and CKKS

SEAL is the most widely used FHE library. It supports two schemes from Module 11:

BFV (exact integer arithmetic):

• Plaintexts are integers mod $t$

• Operations are exact: $\text{Dec}(\text{Enc}(a) \oplus \text{Enc}(b)) = a + b$ (exactly)

• Noise budget decreases with each operation (especially multiplication)

• Use case: counting, voting, exact database queries

CKKS (approximate real-number arithmetic):

• Plaintexts are real/complex numbers

• Operations are approximate: result has a small rounding error

• Use case: machine learning, scientific computing, statistics

# Toy example: encrypted polynomial evaluation (BFV-style)
# f(x) = 3x^2 + 2x + 1
# In SEAL, this would use evaluator.square(), evaluator.multiply_plain(),
# evaluator.add(). We simulate the noise budget.

print('=== Encrypted Polynomial Evaluation: f(x) = 3x^2 + 2x + 1 ===')
print()

# Simulate BFV noise budget (bits)
initial_budget = 54  # typical for poly_modulus_degree=4096
mul_cost = 14        # bits consumed per multiplication
add_cost = 0         # addition is essentially free in noise terms

x_val = 7
budget = initial_budget

print(f'Input: x = {x_val}')
print(f'Initial noise budget: {budget} bits')
print()

# Step 1: Enc(x)
print(f'Step 1: Encrypt x = {x_val}')
print(f'  Noise budget: {budget} bits')

# Step 2: x^2 = x * x (one multiplication)
budget -= mul_cost
x_sq = x_val^2
print(f'Step 2: x^2 = {x_val}^2 = {x_sq}  [multiply, budget: {budget} bits]')

# Step 3: 3*x^2 (plaintext-ciphertext multiply, cheaper)
budget -= mul_cost // 2  # plain multiply is cheaper
term1 = 3 * x_sq
print(f'Step 3: 3*x^2 = {term1}  [plain multiply, budget: {budget} bits]')

# Step 4: 2*x (plaintext-ciphertext multiply)
budget_2x = initial_budget - mul_cost // 2
term2 = 2 * x_val
print(f'Step 4: 2*x = {term2}  [plain multiply, separate chain]')

# Step 5: 3x^2 + 2x (addition, free)
partial = term1 + term2
budget -= add_cost
print(f'Step 5: 3x^2 + 2x = {partial}  [add, budget: {budget} bits]')

# Step 6: + 1 (add plaintext)
result = partial + 1
print(f'Step 6: + 1 = {result}  [add plain, budget: {budget} bits]')

print(f'\nFinal result: f({x_val}) = {result}')
print(f'Expected: 3*{x_val}^2 + 2*{x_val} + 1 = {3*x_val^2 + 2*x_val + 1}')
print(f'Remaining noise budget: {budget} bits (> 0, so decryption succeeds)')

Google's FHE Compiler

Google's transpiler takes standard C++ code and automatically compiles it to FHE circuits. The programmer writes normal code; the compiler handles the cryptography.

Example: an encrypted string capitalization function.

// Original C++ (Google FHE compiler input)
#pragma hls_top
char capitalize(char c) {
    if (c >= 'a' && c <= 'z') {
        return c - 32;  // ASCII lowercase to uppercase
    }
    return c;
}

The compiler transforms this into a Boolean circuit using TFHE gates, where each bit of the input and output is encrypted separately. The if statement becomes a multiplexer circuit.

# Simulating what Google's FHE compiler does:
# Convert a high-level function to a Boolean circuit

print('=== How Google FHE Compiler Works ===')
print()
print('Input:  char capitalize(char c) { ... }')
print()
print('Step 1: Represent char as 8 encrypted bits')
print('        c = [b7, b6, b5, b4, b3, b2, b1, b0]')
print('        Each bi is a TFHE ciphertext encrypting 0 or 1')
print()
print('Step 2: Compile comparison (c >= 97) to Boolean gates')
print('        This becomes a circuit of AND, OR, NOT gates')
print('        Each gate = one TFHE bootstrapping operation')
print()
print('Step 3: Compile subtraction (c - 32) to Boolean gates')
print('        8-bit subtractor = ~40 gates')
print()
print('Step 4: Compile if/else to multiplexer')
print('        result = condition ? (c - 32) : c')
print('        = 8 MUX gates, each using AND + OR')
print()

# Let's count the gates
comparison_gates = 24  # 8-bit comparison
subtraction_gates = 40  # 8-bit subtractor
mux_gates = 24  # 8 MUX (3 gates each)
total_gates = comparison_gates + subtraction_gates + mux_gates

print(f'Total Boolean gates: ~{total_gates}')
print(f'Each gate takes ~10ms with TFHE bootstrapping')
print(f'Total time: ~{total_gates * 10}ms = ~{total_gates * 10 / 1000:.1f}s')
print(f'Cleartext time: ~1 nanosecond')
print(f'Overhead: ~{total_gates * 10 * 1000000}x')
print()
print('This is the cost of computing on encrypted data.')
print('But the programmer wrote NORMAL C++ --- the compiler did the rest.')

Performance Reality

FHE is dramatically slower than cleartext computation. The overhead comes from:

1. Large ciphertexts: a single BFV ciphertext is ~32 KB (vs 4 bytes for an int)

2. Polynomial arithmetic: every operation involves polynomial multiplication mod $q$

3. NTT transforms: each polynomial multiply needs forward NTT, pointwise multiply, inverse NTT

4. Relinearization: after each ciphertext-ciphertext multiply, need to reduce ciphertext size

5. Bootstrapping: the most expensive operation, needed to refresh noise

# Performance comparison across libraries (approximate benchmarks)
print('=== FHE Performance Benchmarks (approximate, 2024 numbers) ===')
print()

# Ciphertext sizes
print('--- Ciphertext Sizes ---')
sizes = [
    ('BFV (n=4096)',     '32 KB',     '4 bytes',  '8,000x'),
    ('BFV (n=16384)',    '512 KB',    '4 bytes',  '128,000x'),
    ('CKKS (n=16384)',   '512 KB',    '8 bytes',  '64,000x'),
    ('TFHE',             '2 KB/bit',  '1 bit',    '16,000x'),
]
for scheme, ct_size, pt_size, expansion in sizes:

print()

# Operation timings
print('--- Operation Timings (single core) ---')
timings = [
    ('BFV Addition',         '~0.01 ms',   '~0.3 ns',    '~30,000x'),
    ('BFV Multiplication',   '~5 ms',      '~0.3 ns',    '~15,000,000x'),
    ('CKKS Addition',        '~0.01 ms',   '~0.5 ns',    '~20,000x'),
    ('CKKS Multiplication',  '~10 ms',     '~1 ns',      '~10,000,000x'),
    ('TFHE Bootstrap',       '~10 ms',     '~0.3 ns',    '~30,000,000x'),
]
for op, fhe_t, plain_t, overhead in timings:

print()
print('Multiplication is the bottleneck: 10-15 MILLION times slower.')
print('This is why minimizing multiplicative depth is so important.')

# What has improved and what remains challenging
print('=== FHE Performance Evolution ===')
print()

evolution = [
    (2009, 'Gentry',   '~30 min / bootstrap',  'Proof of concept'),
    (2011, 'BGV',      '~1 min / multiply',    'Modulus switching'),
    (2015, 'HElib',    '~4 s / AES block',     'SIMD batching'),
    (2016, 'TFHE',     '~13 ms / gate',        'Gate bootstrapping'),
    (2020, 'SEAL 3.6', '~5 ms / multiply',     'Optimized NTT'),
    (2022, 'Concrete', '~8 ms / bootstrap',    'Programmable bootstrap'),
    (2024, 'GPU FHE',  '~0.5 ms / multiply',   'GPU acceleration'),
]

for year, system, speed, innovation in evolution:

print()
print('From 30 minutes per bootstrap (2009) to <1 millisecond on GPU (2024).')
print('That is a >1,000,000x improvement in 15 years.')
print('But FHE is still 10,000x-1,000,000x slower than cleartext.')
print()
print('Hardware accelerators (DARPA DPRIVE, Intel, FHE-on-FPGA) aim to')
print('close the remaining gap by 10-100x in the next few years.')

Detailed Library Comparison

Each library has different strengths depending on your use case.

# Detailed comparison
print('=== Library Comparison for Common Use Cases ===')
print()

use_cases = [
    ('Encrypted ML inference',     'SEAL (CKKS) or Concrete ML',
     'CKKS handles real numbers; Concrete ML auto-compiles models'),
    ('Encrypted voting/counting',  'SEAL (BFV) or OpenFHE (BGV)',
     'Exact integer arithmetic, additive homomorphism'),
    ('Encrypted string processing','Google FHE (TFHE)',
     'Bit-level operations with gate bootstrapping'),
    ('Encrypted database queries',  'OpenFHE or SEAL',
     'Depends on query type: BFV for exact, CKKS for approximate'),
    ('Privacy-preserving genomics', 'HElib or Lattigo',
     'BGV with deep SIMD batching for sequence comparison'),
    ('Encrypted neural network',    'Concrete ML or SEAL + EVA',
     'Auto-compilation from PyTorch/sklearn to FHE'),
]

for use_case, library, reason in use_cases:
    print(f'Use case: {use_case}')
    print(f'  Best library: {library}')
    print(f'  Why: {reason}')
    print()

Concept Map

Module 11 Concept	Production Library Feature
BGV/BFV (integer FHE)	SEAL scheme_type::bfv, OpenFHE BGV
CKKS (approximate FHE)	SEAL scheme_type::ckks, Lattigo CKKS
Bootstrapping	TFHE (every gate), OpenFHE (configurable)
Noise budget	SEAL invariant_noise_budget()
Relinearization	SEAL evaluator.relinearize()
Modulus switching	SEAL evaluator.mod_switch_to_next()
NTT	Used internally by all libraries for fast polynomial multiply
SIMD batching	SEAL BatchEncoder, HElib EncryptedArray
Plaintext modulus $t$	SEAL set_plain_modulus()
Polynomial degree $n$	SEAL set_poly_modulus_degree()

# Summary: the path from Module 11 theory to production
print('=== From Module 11 Theory to Production ===')
print()
print('Module 11 taught you:                  Production libraries handle:')
print('Paillier additive homomorphism     --> Used directly for simple aggregation')
print('BGV modulus switching               --> SEAL/OpenFHE automatic mod switching')
print('BFV scaling and noise               --> SEAL BFV with invariant_noise_budget')
print('CKKS approximate arithmetic         --> SEAL CKKS with rescaling')
print('Noise growth per operation          --> Automatic noise tracking & warnings')
print('Bootstrapping concept               --> TFHE: every gate; OpenFHE: on demand')
print('Polynomial ring Z_q[x]/(x^n + 1)   --> NTT-accelerated polynomial arithmetic')
print()
print('The theory from Module 11 is EXACTLY what these libraries implement.')
print('Understanding the math lets you:')
print('  - Choose the right scheme (BFV vs CKKS vs TFHE)')
print('  - Select parameters (n, q, t) for your use case')
print('  - Understand error messages about noise budget exhaustion')
print('  - Optimize circuits to minimize multiplicative depth')

Summary

Aspect	Detail
SEAL	Microsoft's BFV/CKKS library, most popular, MIT license
OpenFHE	DARPA-funded, supports all schemes, most comprehensive
TFHE/Concrete	Zama's gate-level bootstrapping, best for Boolean circuits
Google FHE	Compiler that transpiles C++ to FHE circuits automatically
Performance	10,000x--1,000,000x overhead, improving rapidly
Hardware	DARPA DPRIVE and Intel accelerators aim for 10--100x speedup
Key insight	Module 11's math (BGV/BFV/CKKS/noise) is exactly what these libraries implement

FHE has transitioned from a theoretical curiosity to an engineering discipline. The math from Module 11 --- polynomial rings, noise budgets, modulus switching, bootstrapping --- is the foundation that every production library builds on. Understanding the theory lets you be an informed user of these tools, not just a black-box consumer.

---

Back to Module 11: Homomorphic Encryption