Homomorphic Encryption

The idea: a glove box for data

Ordinary encryption is a one-way street. To do anything useful with encrypted numbers — add them, multiply them, run a model over them — you decrypt first, compute on the plaintext, then re-encrypt. For the brief moment of computation, the data is exposed, and whoever runs the computation (a cloud provider, an analytics firm) can see it.

Homomorphic encryption breaks that rule. It is the cryptographic equivalent of a sealed glove box: the data goes in locked, you reach through the gloves and rearrange it without ever opening the box, and what comes out is the locked answer. The server doing the work never sees a single plaintext value. You take the result home and only your secret key unlocks it.

The word "homomorphic" comes from algebra: a homomorphism is a structure-preserving map. A scheme is homomorphic for an operation ⊕ on plaintexts if there's a matching operation ⊗ on ciphertexts such that:

Dec( Enc(a) ⊗ Enc(b) ) = a ⊕ b

If that holds for both addition and multiplication, you can build any arithmetic circuit — and therefore any computation — out of those two gates. That is the holy grail called fully homomorphic encryption, and it stood as an open problem for 31 years between Rivest, Adleman, and Dertouzos posing it in 1978 and Craig Gentry solving it in his 2009 PhD thesis.

How the math actually works

The earliest homomorphic schemes were "partial" — they got one operation for free as an accident of their structure. Textbook RSA is multiplicatively homomorphic because (m₁e)·(m₂e) = (m₁m₂)e mod n: multiply two ciphertexts and you've multiplied the plaintexts. Paillier (1999) is additively homomorphic: multiplying ciphertexts adds the plaintexts. But neither gives you both, so neither can run an arbitrary program.

Modern fully homomorphic schemes are built on lattices and the Learning With Errors (LWE) problem. The trick is to bury each message in deliberate random noise. A simplified symmetric LWE ciphertext for a bit m ∈ {0,1} is a pair:

c = (a, b)  where  b = ⟨a, s⟩ + e + m·⌊q/2⌋   (mod q)

Here a is a random vector, s is the secret key, e is a small error sampled from a narrow distribution, and q is the modulus. To decrypt, compute b − ⟨a, s⟩ = e + m·⌊q/2⌋ and round: if it's near 0 the bit was 0, if near q/2 the bit was 1. The error e is what makes the problem hard — recovering s from many such samples is the LWE problem, conjectured hard even for quantum computers.

Now the magic. Add two ciphertexts componentwise and the messages add — but so do the noises. Multiply and the messages multiply, but the noise grows much faster (roughly multiplicatively). Every operation eats into a finite noise budget. When the accumulated error exceeds q/4, the rounding step in decryption flips and the plaintext is corrupted. So a raw lattice scheme is only somewhat homomorphic: it can evaluate circuits up to a bounded multiplicative depth.

Gentry's breakthrough was bootstrapping: take the scheme's own decryption procedure, express it as a circuit, and evaluate that circuit homomorphically on a noisy ciphertext using an encrypted copy of the secret key. Decryption removes noise; doing it under encryption produces a fresh ciphertext of the same message with the noise reset to baseline. Run bootstrapping periodically and you can compute forever — turning a somewhat-homomorphic scheme into a fully homomorphic one.

When homomorphic encryption is worth it

• Outsourced computation on sensitive data — a hospital sends encrypted genomes to a cloud, which runs a diagnostic model and returns an encrypted score it never read.
• Private machine-learning inference — a user sends an encrypted image; the server runs a neural network and returns an encrypted prediction. CKKS is the workhorse here.
• Encrypted database queries and private set intersection — match records or count overlaps without revealing either party's data.
• Federated analytics — aggregate encrypted statistics from many parties (additive Paillier alone often suffices, and it's fast).
• Secure voting and auctions — sum encrypted ballots or bids; only the tally is decrypted.

Skip it when latency or throughput matters and the threat model allows trusted hardware. If the bottleneck is "the cloud could peek," a hardware enclave (SGX, TDX) or multi-party computation (MPC) is usually orders of magnitude faster. Reach for FHE specifically when you need a single non-interactive party to compute and you cannot trust its hardware — the unique selling point is that the server stays oblivious with zero rounds of interaction.

FHE vs the alternatives

	FHE (BGV/CKKS/TFHE)	Paillier (additive PHE)	Secure MPC	Trusted enclave (SGX)	Zero-knowledge proof
Operations supported	Any circuit (+ and ×)	Addition only	Any circuit	Anything (native CPU)	Verify, not compute
Interaction rounds	0 (non-interactive)	0	Many (per gate/round)	0	1 (or 0, non-interactive)
Slowdown vs plaintext	10³–10⁶×	~10²× (one op)	10–10³× + network	~1.1–2×	10²–10⁶× to prove
Ciphertext size	KB–MB per value	~512 bytes	secret shares	plaintext in memory	proof KB–MB
Trust assumption	None (math only)	None (math only)	Honest majority / no collusion	Trust the CPU vendor	None (soundness)
Quantum-safe	Yes (lattice)	No (factoring)	Depends on primitives	N/A (hardware)	Scheme-dependent
Best for	Non-interactive private compute	Encrypted sums/voting	Joint compute, low latency	Throughput with HW trust	Proving a result is correct

The headline trade-off is interaction versus trust. MPC matches FHE's "no trusted party" guarantee but needs the parties online and chatting for every layer of the circuit; FHE pushes the whole circuit onto one server with zero rounds, paying for it in raw arithmetic cost. Enclaves are nearly free but you must trust the silicon — and side-channel attacks keep breaking that assumption.

What the numbers actually say

• Gentry's original 2009 scheme was a proof of concept, not a tool: a single bootstrapping operation took around 30 minutes, and a re-encryption could need gigabytes of public key material.
• A single TFHE gate bootstrapping on a modern CPU runs in roughly 10–13 milliseconds — fast enough for boolean circuits, but a 32-bit integer multiply is thousands of gates, so still seconds of work.
• Ciphertext expansion is brutal. A single encrypted real number in CKKS lives inside a polynomial with thousands of coefficients; one ciphertext is typically tens of kilobytes to a few megabytes, versus 8 bytes for the plaintext double — an expansion of 1,000× or more.
• Encrypted neural-network inference on a small model (e.g. CryptoNets on MNIST) took on the order of hundreds of seconds per batch in early work; modern CKKS libraries and GPU acceleration have pushed comparable workloads down to seconds, still 10⁴–10⁶× the plaintext cost.
• SIMD batching changes the math. CKKS and BGV pack thousands of plaintext slots into one ciphertext, so a single homomorphic operation processes (say) 4,096 numbers at once — the per-element overhead is far smaller than the per-ciphertext overhead suggests.

A JavaScript model: Paillier additive homomorphism

Full lattice FHE is too heavy to show in a snippet, but the partially homomorphic Paillier cryptosystem captures the essence — multiplying ciphertexts adds plaintexts — in a few lines. This uses BigInt; it is a teaching model, not production code (no safe primes, no constant-time arithmetic).

// --- modular helpers (BigInt) ---
const mod = (a, n) => ((a % n) + n) % n;
function powmod(b, e, n) {
  let r = 1n; b = mod(b, n);
  while (e > 0n) { if (e & 1n) r = (r * b) % n; b = (b * b) % n; e >>= 1n; }
  return r;
}
function inv(a, n) {            // modular inverse via extended Euclid
  let [t, nt, r, nr] = [0n, 1n, n, mod(a, n)];
  while (nr) { const q = r / nr; [t, nt] = [nt, t - q * nt]; [r, nr] = [nr, r - q * nr]; }
  return mod(t, n);
}

// --- key generation (toy primes; real keys are 2048+ bits) ---
function keygen(p = 17n, q = 19n) {
  const n = p * q, n2 = n * n;
  const lambda = (p - 1n) * (q - 1n);      // Euler totient φ(n); works as λ since g = n+1
  const g = n + 1n;                         // standard simplification
  const L = x => (x - 1n) / n;
  const mu = inv(L(powmod(g, lambda, n2)), n);
  return { pub: { n, n2, g }, sec: { lambda, mu, n } };
}

function encrypt(pub, m, r = 7n) {          // r should be random & coprime to n
  const { n, n2, g } = pub;
  return (powmod(g, m, n2) * powmod(r, n, n2)) % n2;
}
function decrypt(sec, c) {
  const { lambda, mu, n } = sec;
  const L = x => (x - 1n) / n;
  return mod(L(powmod(c, lambda, n * n)) * mu, n);
}

// --- the homomorphism: multiply ciphertexts == ADD plaintexts ---
const { pub, sec } = keygen();
const ca = encrypt(pub, 15n);
const cb = encrypt(pub, 20n);
const cSum = (ca * cb) % pub.n2;            // never decrypts a or b!
console.log(decrypt(sec, cSum));            // => 35n  (15 + 20)

// scalar multiply for free: raise a ciphertext to a constant
const cTriple = powmod(ca, 3n, pub.n2);
console.log(decrypt(sec, cTriple));         // => 45n  (15 * 3)

Notice what the server never touched: it combined ca and cb by plain multiplication and exponentiation, learning nothing about 15 or 20. Only the holder of sec can read the 35. That is the whole game — Paillier just stops at addition, while FHE keeps going to multiplication and beyond.

A Python model: the noise budget and bootstrapping

The part Paillier can't illustrate is noise — the thing that limits FHE depth and motivates bootstrapping. This toy symmetric LWE-style scheme over a single integer shows how each operation grows the error, and why decryption eventually fails.

q = 1 << 20          # ciphertext modulus
half = q // 2        # bit 0 lives near 0, bit 1 near q/2
thresh = q // 4      # noise tolerance: |error| must stay below q/4

# A ciphertext is (key + m*half + e) mod q, masking the message m with the
# secret key. We carry the noise magnitude e alongside so the demo is exact and
# reproducible. Decryption removes the mask and rounds.
def enc(m, key, noise=8):
    return ((key + m * half + noise) % q, noise)   # (ciphertext, noise)

def dec(c, key):
    v = (c[0] - key) % q
    return 0 if min(v, q - v) < thresh else 1

def add(c1, c2, key):            # homomorphic add: messages add, noise ADDS
    return ((c1[0] + c2[0] - key) % q, c1[1] + c2[1])

key = 123456

# A shallow circuit decrypts correctly...
acc = enc(1, key)
for _ in range(3):
    acc = add(acc, enc(0, key, 8), key)      # noise creeps up slowly
print("shallow:", dec(acc, key), "noise:", acc[1])   # -> 1, still correct

# ...but keep piling on noisy operations and decryption flips:
acc = enc(1, key)
for _ in range(40):
    acc = add(acc, enc(0, key, 8000), key)   # noise piles up past q/4
print("deep:", dec(acc, key), "noise:", acc[1])      # -> 0, the bit is wrong

# BOOTSTRAPPING (concept): run dec() *homomorphically* under an encrypted key,
# producing a fresh ciphertext of the same bit with noise reset to baseline.
def bootstrap(c, key, fresh_noise=8):
    m = dec(c, key)              # in real FHE this is done ENCRYPTED
    return enc(m, key, fresh_noise)

# Refresh periodically — before noise crosses the threshold — and compute forever:
acc = enc(1, key)
for _ in range(40):
    acc = add(acc, enc(0, key, 8000), key)
    if acc[1] > thresh // 2:
        acc = bootstrap(acc, key)            # noise back to ~baseline
print("with bootstrap:", dec(acc, key), "noise:", acc[1])

In a real scheme you never call dec() in the clear — that would defeat the purpose. Bootstrapping evaluates the decryption circuit homomorphically, using an encrypted secret key, so the noise resets without anyone ever seeing the plaintext. The toy above just shows the bookkeeping: noise accumulates, threatens the answer, and bootstrapping restores headroom.

The schemes worth knowing

Paillier / ElGamal (PHE). Partially homomorphic — additive and multiplicative respectively. Decades old, fast, and still the right tool for encrypted sums (e-voting, private aggregation) where you only need one operation.

BGV and BFV. Second-generation leveled schemes (Brakerski-Gentry-Vaikuntanathan, 2012, and Brakerski/Fan-Vercauteren). Exact integer arithmetic over a chosen plaintext modulus, with SIMD "batching" that packs thousands of values per ciphertext. The default choice when you need exact results.

CKKS. Cheon-Kim-Kim-Song (2017). Approximate arithmetic on real and complex numbers — it folds encryption noise into fixed-point rounding error, like floating point. This makes it the dominant scheme for privacy-preserving machine learning, where small errors are acceptable.

GSW and TFHE. The Gentry-Sahai-Waters approach and its fast descendant TFHE (Chillotti et al., 2016) bootstrap a single boolean gate in milliseconds. Best when the computation is naturally a boolean circuit with comparisons and branches encoded as lookups.

Scheme switching. Modern frameworks (e.g. the CHIMERA/Concrete line of work) convert ciphertexts between TFHE, CKKS, and BFV mid-computation, using each where it's strongest — fast gates in TFHE, batched arithmetic in CKKS.

Common bugs and edge cases

• Exhausting the noise budget. Each multiplication roughly squares the noise. Stack too many before bootstrapping (or before your leveled parameters allow) and decryption silently returns garbage — no error, just a wrong number.
• Trying to branch on encrypted data. There is no if (encA > encB). Comparisons must be turned into arithmetic — a multiplexer sel·a + (1−sel)·b or a polynomial approximation of the sign function. Every path of the program runs.
• Reusing randomness on encryption. The fresh random term in each ciphertext is what makes the scheme semantically secure. Drop it or reuse it and identical plaintexts produce identical ciphertexts, leaking equality.
• Forgetting CKKS is approximate. Comparing a decrypted CKKS result to an exact value with == will fail; you must compare within a tolerance, and you must budget the precision (scale) up front.
• Underestimating parameter selection. Picking the polynomial degree, modulus chain, and noise distribution is where security and performance live; get them wrong and you either lose security or run out of multiplicative depth. Libraries ship parameter presets for exactly this reason.
• Confusing "homomorphic" with "verified." FHE hides the inputs but does not prove the server ran the right circuit. If you need integrity too, you must layer a verifiable-computation or zero-knowledge proof on top.