Homomorphic Encryption, in depth: Paillier, LWE noise budgets, BFV, BGV, CKKS, TFHE and bootstrapping

Additive encryption with Paillier

Paillier (1999) is additively homomorphic and is still the right tool when all you need is encrypted sums. Key generation picks primes p and q, sets n = pq, uses g = n + 1, and computes lambda = lcm(p - 1, q - 1) and mu = lambda^-1 mod n. Encryption of m below n with random r coprime to n is c = g^m r^n mod n^2. Decryption is m = L(c^lambda mod n^2) mu mod n, where L(u) = (u - 1) / n. Because g = n + 1, the binomial theorem gives g^m = 1 + mn mod n^2, which is why L recovers m.

import math

p, q = 11, 13                        # toy primes; real n is 2048 bits or more
n, n2, g = p * q, (p * q) ** 2, p * q + 1
lam = math.lcm(p - 1, q - 1)
mu = pow(lam, -1, n)

def enc(m, r):  return pow(g, m, n2) * pow(r, n, n2) % n2
def dec(c):     return (pow(c, lam, n2) - 1) // n * mu % n

c1, c2 = enc(5, 7), enc(9, 10)
assert dec(c1 * c2 % n2) == 14       # multiply ciphertexts -> add plaintexts
assert dec(pow(c1, 3, n2)) == 15     # power by a constant -> multiply plaintext by it

With these toy primes n = 143, n^2 = 20,449, lambda = 60 and mu = 31. Enc(5) with r = 7 is 8,439 and Enc(9) with r = 10 is 15,773. Their product modulo 20,449 is 5,806, which decrypts to 14, and 8,439 cubed modulo 20,449 is 19,456, which decrypts to 15. Sums wrap modulo n, so size n far above any total you will form. What Paillier cannot do is multiply two ciphertexts together, which rules out most interesting functions. It is also malleable by design: anyone can add to an encrypted value, so it must be paired with signatures or proofs wherever tampering matters. The arithmetic itself is modular exponentiation over a 4,096-bit modulus for a 2,048-bit n.

Noise: LWE from first principles

Every practical FHE scheme is built on learning with errors (LWE) or its ring variant. The idea fits in a few lines. The secret key is a vector s modulo q. To encrypt a small message m modulo t, pick a random vector a, a small random error e, and publish (a, b) with b = a . s + e + Delta m, where Delta = q / t. Without s, b looks uniformly random; that is the LWE assumption. With s, subtract a . s, leaving Delta m + e, and round to the nearest multiple of Delta. Decryption is correct as long as the error stays below Delta / 2.

import random
random.seed(12)
N, Q, T = 16, 2**16, 16
DELTA = Q // T                                   # 4096; decryption fails once |noise| >= 2048
s = [random.randrange(Q) for _ in range(N)]

def enc(m, bound=4):
    a = [random.randrange(Q) for _ in range(N)]
    e = random.randint(-bound, bound)
    return a, (sum(x * y for x, y in zip(a, s)) + e + DELTA * m) % Q

def dec(c):
    a, b = c
    return round(((b - sum(x * y for x, y in zip(a, s))) % Q) / DELTA) % T

def add(c1, c2):  return [(x + y) % Q for x, y in zip(c1[0], c2[0])], (c1[1] + c2[1]) % Q
def smul(k, c):   return [k * x % Q for x in c[0]], k * c[1] % Q

Adding two ciphertexts adds their errors; multiplying by a constant k multiplies the error by k. With seed 12, the first ciphertext, c = enc(1), carries an error of -2. Multiplying it by 1,000 gave error -2,000 and still decrypted to 1,000 mod 16 = 8. Multiplying by 1,100 gave error -2,200, past the 2,048 threshold, and it decrypted to 11 instead of 12. Nothing signalled the failure: the result was simply wrong. That is the central fact of FHE engineering. Every operation consumes part of a noise budget, multiplying two ciphertexts consumes far more than adding, and when the budget runs out you get garbage, not an error. This toy is insecure (N = 16 is trivially breakable) and has no ciphertext-by-ciphertext multiply; real schemes add that with a tensor product followed by relinearisation, which uses an evaluation key to shrink the result back to normal size.

The lattice families

Real schemes move to polynomials. In ring LWE the vectors become polynomials in Z_q[X] / (X^N + 1) with N a power of two, so one ciphertext carries N coefficients and polynomial multiplication is done in O(N log N) with the negacyclic number theoretic transform. The large modulus q is a product of machine-word primes and every operation runs per prime, the residue number system that rests on the Chinese remainder theorem. On top of that ring, four families dominate:

BFV, BGV and CKKS are batched: one ciphertext holds thousands of values in slots, an addition or multiplication acts on all slots at once, and rotations move values between slots using Galois keys. They are fast per value but awkward for anything non-polynomial, since a comparison must be approximated by a polynomial. TFHE works on one small value at a time but makes any lookup table cheap, so comparisons and ReLU are natural. Mature libraries include Microsoft SEAL (BFV, BGV, CKKS), OpenFHE (BFV, BGV, CKKS and the FHEW/TFHE family), Zama's TFHE-rs and Lattigo in Go.

Bootstrapping

A levelled scheme supports a fixed multiplicative depth set by q: each multiplication eats roughly one prime of the modulus chain, and when the chain is exhausted you must stop. Bootstrapping is Gentry's trick for continuing. The server holds an encryption of the secret key, and it homomorphically evaluates the decryption circuit on the noisy ciphertext. The output is a fresh encryption of the same message, with noise set by the depth of decryption rather than by the history of the computation. If the decryption circuit plus one more useful operation fits in the budget, computation can continue for ever. That is what makes a scheme fully homomorphic. It also introduces an extra assumption, circular security, because the key is encrypted under itself.

Bootstrapping is the most expensive operation in FHE by a wide margin in the batched schemes, so the design rule is to choose the depth of your function first and bootstrap as rarely as possible, or not at all. Many deployed systems are levelled: they fix the function, pick parameters deep enough for it, and never bootstrap.

Choosing parameters

Security comes from the ratio of ring dimension N to modulus size log q: a larger q gives more noise budget but weaker security for the same N. The HomomorphicEncryption.org standard tabulates the largest safe q. SEAL encodes its 128-bit classical security bounds as:

Pick parameters in this order. Fix the plaintext precision you need. Count the multiplicative depth of your function, not its number of operations. Size q to cover that depth plus headroom, then take the smallest N whose bound allows it. Doubling N roughly doubles ciphertext size and more than doubles multiply time, so a function written with half the depth can be several times cheaper. Squaring by repeated multiplication in a balanced tree, rather than in a chain, is the classic depth saving: x^8 needs depth 3, not 7.

Architecture and a worked aggregation

A concrete example: several hospitals want the mean of a lab value across their patients without revealing per-hospital values to a central aggregator. With Paillier, each site encrypts its sum and count under a coordinator's public key, the aggregator multiplies the ciphertexts, and the coordinator decrypts only the totals. Nothing below needs a multiplication of ciphertexts, so the additive scheme is enough and far cheaper than FHE:

# aggregator: no secret key
total_c = 1
count_c = 1
for site in sites:
    total_c = total_c * site.enc_sum   % n2      # adds encrypted sums
    count_c = count_c * site.enc_count % n2      # adds encrypted counts
# coordinator: holds the secret key, sees only aggregates
mean = dec(total_c) / dec(count_c)

As long as the coordinator and aggregator do not collude, neither learns any single site's value; but the coordinator can decrypt any ciphertext it is handed, so the protocol must stop the aggregator forwarding one. That is a key-management problem, not a cryptographic one, and it is where most real designs need care: threshold decryption splits the key so no single party can decrypt alone.

Failure modes

• Silent noise overflow. As the toy showed, an exhausted budget returns wrong plaintext with no error. Track depth statically and test with the exact production parameters.
• CKKS precision drift. CKKS results are approximate by design; errors accumulate with depth and with large values. Measure error against a plaintext reference on real data ranges.
• Sharing CKKS decryptions. Decrypted CKKS outputs contain noise that reveals information about the key (Li and Micciancio, 2021). Never return raw CKKS decryptions to an untrusted party without noise flooding.
• Insecure parameters. A q larger than the table allows for your N quietly lowers security. Use library presets or a lattice estimator, never hand-picked numbers.
• Data-dependent control flow. The server cannot branch on encrypted values. Every if-statement becomes evaluating both branches and selecting arithmetically, which changes the cost model completely.
• Integrity. HE does not stop a server returning Enc(0) or running a different function. Add verifiable computation or redundancy if correctness is at stake.
• Ciphertext expansion. Ciphertexts are often orders of magnitude larger than the data; bandwidth and storage, not CPU, can be the real bill.

Trade-offs

For a side-by-side of HE, enclaves and MPC around a hosted model, read secure inference.

What to do next

1. Write down the function you want to evaluate and its multiplicative depth. If it needs only additions and constant multiplies, use Paillier and stop.
2. Run the Paillier and toy LWE code above, then push the toy past its noise threshold yourself to see the silent failure.
3. For exact integer work start with BFV in SEAL or OpenFHE; for real-valued ML, CKKS; for comparisons and lookups, TFHE-rs or OpenFHE's FHEW/TFHE schemes.
4. Choose parameters from library presets at 128-bit security and check them against the table.
5. Compare every encrypted result against a plaintext reference across your real value ranges before trusting it.
6. Design key custody (who decrypts, threshold or not) before the cryptography, and add an integrity check if a lying server would hurt you.