# How Fully Homomorphic Encryption Would Break: The Seams Above the Lattice
> Fully homomorphic encryption computes on data it never decrypts. Its likeliest failure is not the post-quantum lattice beneath it, but the scheme layer above.
*Published: 2026-07-20*
*Canonical: https://paragmali.com/blog/how-fully-homomorphic-encryption-would-break-the-seams-above*
*© Parag Mali. All rights reserved.*
---
Fully homomorphic encryption lets you compute on data you never decrypt, on a lattice foundation no known quantum attack can break [@regev-lwe]. Yet its likeliest failure is not that foundation. It is the *scheme layer* above it: a noise budget that must not overflow, a circular-security debt every bootstrap silently signs, and above all the **IND-CPA-D line**, where in 2021 Li and Micciancio showed that *releasing a correct decryption* from the approximate scheme CKKS hands an attacker the secret key -- a passive, polynomial-time, total break that never solves a lattice [@limicciancio-21]. The repair (worst-case noise flooding) broke in 2024 from a *single* released decryption [@guo-usenix-24], the *exact* schemes fell the same year through decryption failures [@checri-crypto-24], and the fixes are a live, unfinished discipline [@aahe-24]. This is a structural map of where FHE breaks first -- and why it is the seams, not the floor.
## 1. A Strongbox You Can Compute Inside
Fully homomorphic encryption is the closest thing cryptography has to magic: a strongbox you can reach inside and compute on -- add, multiply, run a whole statistical model -- without ever opening it, and without the machine doing the work ever seeing what it holds. Its foundation is a lattice problem that not even a quantum computer is known to break [@regev-lwe].
And yet the likeliest way this system fails has nothing to do with that foundation. In 2021, Baiyu Li and Daniele Micciancio showed that computing an average over encrypted data and publishing the correct, decrypted answer -- the entire point of the exercise -- may have just handed the attacker your secret key [@limicciancio-21].
That sentence should feel wrong. If the answer is correct, how can it also be a leak? The resolution is the whole story of this article, and it starts with a single idea: **FHE's security is layered.** At the bottom sits the lattice -- the Ring-LWE assumption most FHE schemes use, part of the same Module-LWE family that underpins the post-quantum standard ML-KEM [@lpr-rlwe].
That base is a catastrophic single point of failure in theory, but in fifteen years nothing has cracked it. Everything that has actually broken lives *above* it, in the machinery bolted on to turn a hard lattice problem into a usable computer.
> **Key idea:** The floor holds; the seams leak. FHE's base lattice is a catastrophic-but-hypothetical single point of failure that has never fallen. Its likeliest real failures are all in the scheme layer above -- the noise budget, the circular-security debt, the IND-CPA-D line, and the drift between chosen parameters and community security levels.
Hold two images in mind, because the article turns on the difference between them. In the first, you keep multiplying ciphertexts until an internal error term grows past a threshold, and decryption returns not a wrong number but *garbage* -- noise where your answer should be. In the second, decryption works perfectly, returns exactly the average you asked for, and *that correct value* is the linear equation an attacker needed. The first image is a correctness failure. The second is a key leak. Almost everyone conflates them, and the conflation is the topic's central trap.
This piece walks four seams in order: the **noise budget** as a correctness cliff; the **circular-security debt** that bootstrapping signs to compute forever; the **IND-CPA-D line** where a released decryption returns the key; and the **parameter drift** between the numbers a deployment chose and the community's security tables. Each is a place FHE would break before the lattice does. The spoiler is already on the table: not one of these breaks touches the lattice.
Before we can rank where FHE breaks, we have to draw a clean line around what "break" even means here -- and deliberately put the one thing everyone fears, the lattice, inside a black box.
## 2. The Line We Draw, and the Black Box
"Break" is an ambiguous word, so let us fix it. This article is Track A: **structural cryptanalysis**. It asks where FHE would fail *by mathematics and definition* -- where the math runs out, where a proof rests on an assumption that might be false, where a security definition quietly models the wrong game. It does not ask where a specific library shipped a bug or where a power trace leaked a bit.
> **Note:** This is a structural analysis. Timing and power side channels, fault-injection attacks, and buggy library implementations are real ways FHE deployments fail, but they are not *structural* -- they are the charter of the sibling real-life track. We name that boundary once, here, and then stay on the side of mathematics and definitions.
To see the scheme layer clearly, we put the lattice inside a black box and assume it is hard. That is not a dodge; it is the honest reflection of what fifteen years of cryptanalysis found. So the analysis needs only the shape of what is inside the box, not its internals.
Encryption that supports *both* addition and multiplication on ciphertext, without a bound on how many, so that any computation can run on encrypted data and only the holder of the secret key can read the result [@gentry-09].
The base assumption of lattice cryptography. A ciphertext is, in effect, a *noisy linear equation in the secret key*: recover the key and you have solved a lattice problem believed hard even for quantum computers. Ring-LWE is the efficient algebraic variant most FHE schemes actually use [@regev-lwe] [@lpr-rlwe].
The one mechanical fact we carry forward is that every ciphertext hides a small error term, the **noise**, and that noise is where both the correctness story and the security story begin.
The margin between a ciphertext's growing internal error and the decryption threshold -- a scheme-dependent fraction of the modulus $q$ (roughly $q/2$; precisely $q/4$ for a single-bit message and $q/(2t)$ in general). Every homomorphic operation spends some of it; cross that threshold and decryption no longer returns the right value [@gentry-09].
That noise budget plays *two* roles, and conflating them is the mistake this whole article is built to prevent. As a **correctness** budget, it bounds how much you can compute before the answer turns to garbage. As a **security** surface, the residual error left in a ciphertext is a function of the secret key -- so if you ever *reveal* that error, you have revealed a linear constraint on the key. The first role is famous. The second is where FHE actually breaks.
flowchart TD
subgraph SEAMS["Scheme layer -- the seams that leak"]
N["Noise budget: overflow corrupts the answer"]
K["Circular-security / KDM debt of bootstrapping"]
D["IND-CPA-D: a released decryption returns the key"]
P["Parameter drift vs community security levels"]
end
subgraph FLOOR["Base lattice -- the floor that holds"]
L["Ring-LWE and Module-LWE, assumed hard, post-quantum"]
end
N --> L
K --> L
D --> L
P --> L
The floor was assumed hard from the very first day FHE existed. So was the first seam. To see why, we go back to a thirty-year-old question -- and to the answer that arrived already in debt.
## 3. The Question, and the Noise That Came With the Answer
In 1978, one year after they co-invented RSA, Ron Rivest and Len Adleman, with Michael Dertouzos, asked a question that would stay open for three decades: could a "data bank" compute on ciphertext it can never read [@rad78]? They called the goal a *privacy homomorphism*. Time-shared computers were new, outsourcing was new, and the privacy problem was obvious -- you hand a machine your data and you have to trust it. RSA already hinted that the idea was not absurd.
RSA, introduced in 1977 (published in 1978), is multiplicatively homomorphic almost by accident: the product of two ciphertexts decrypts to the product of the two plaintexts. That single free operation is exactly why the 1978 privacy-homomorphism question was natural to pose [@rad78].
The trouble was that one free operation is not enough. RSA multiplies but cannot add; later schemes such as Paillier add but cannot multiply [@paillier-99]. Arbitrary computation needs *both*, unboundedly, and every attempt to get both ran into the same wall: each operation injected error into the ciphertext, and after a few multiplications the error drowned the signal. For thirty-one years, "somewhat" homomorphic was the best anyone could do. The community's own retrospective still opens on exactly this lineage, from the 1978 conception to the 2009 breakthrough [@security-guidelines-24].
Then, in 2009, Craig Gentry -- a Stanford PhD student advised by Dan Boneh -- broke the impasse with a move that sounds circular until you see why it works. If a noisy ciphertext could be *refreshed* to low noise without ever exposing the key in the clear, you could compute forever. His mechanism for that refresh is bootstrapping [@gentry-09].
Homomorphically evaluating the scheme's own decryption circuit on a noisy ciphertext, using a published encryption of the secret key, to produce a fresh ciphertext of the same plaintext with the noise reset low. Bootstrapping is the refresh that turns bounded, leveled homomorphic encryption into unbounded FHE [@gentry-09].
Read that definition again, because it plants both of the debts this article collects. To refresh, the scheme runs its *own decryption* homomorphically, which means it must publish an *encryption of the secret key*. And the noise it is fighting never goes away -- bootstrapping only pushes it back down, so the noise budget becomes the permanent weather of every FHE computation.
timeline
title The base holds while the scheme layer keeps breaking
1978 : Rivest, Adleman and Dertouzos pose the privacy-homomorphism question
2005 : Regev introduces LWE, the base assumption
2009 : Gentry builds the first FHE with bootstrapping
2011 to 2017 : BGV, BFV, GSW, FHEW, TFHE and CKKS refine the scheme layer
2021 : Li and Micciancio break CKKS with the IND-CPA-D attack
2022 to 2025 : noise flooding, exact-scheme breaks, application-aware HE and HintLWE
Notice the shape of the timeline. The bottom track -- the base assumption, LWE in 2005 and Ring-LWE just after -- never breaks. The top track keeps breaking and getting re-patched. That asymmetry is not an accident of this diagram; it is the thesis, drawn as history. The base was always assumed hard, and the fragility was always in the machinery on top.
Gentry's breakthrough arrived owing two debts. The first is the one everyone has heard of -- the noise -- and the honest reading of it is not the one you have been told.
## 4. The First Seam: The Noise Budget as a Correctness Cliff
Every ciphertext is a noisy linear equation in the secret key. Addition of two ciphertexts adds their errors; multiplication roughly multiplies them, so noise compounds fastest under multiplication. Decryption works only while the noise stays below that threshold, a scheme-dependent fraction of $q$ on the order of $q/2$. Cross the line and the answer is not slightly wrong -- it is pseudorandom. This is the famous noise budget, and almost everyone reads its danger backwards.
Multiplicative *depth* is the real budget. Additions are cheap because errors merely add; multiplications are what compound the noise toward the ceiling, which is why "how many multiplications deep" is the number that matters, not "how many operations total" [@brakerski-si].
The last fifteen years of scheme design are, from one angle, a single long campaign to spend that budget more slowly. Gentry's 2009 scheme refreshed noise by bootstrapping, made feasible by *squashing* the decryption circuit down to low degree -- at the cost of an extra sparse-subset-sum assumption [@gentry-09]. In 2011, Brakerski and Vaikuntanathan rebuilt FHE on standard LWE with *re-linearization* and *dimension-modulus reduction*, explicitly abandoning squashing [@bv11].
BGV added *modulus switching*: after each multiplication, rescale the ciphertext to a smaller modulus so noise grows only additively across the levels, letting a bounded-depth circuit run with no bootstrapping at all [@bgv]. Brakerski's scale-invariant construction then made noise grow only linearly, $B \to B \cdot \mathrm{poly}(n)$, instead of quadratically, and Fan and Vercauteren ported it to Ring-LWE as BFV, the workhorse exact scheme with tight worst-case noise bounds [@brakerski-si] [@bfv].
A parallel line attacked the refresh cost instead of the growth rate. The Gentry-Sahai-Waters scheme recast homomorphic operations as matrix arithmetic with no evaluation key [@gsw]; FHEW turned that into a bootstrap in about half a second, against roughly six minutes per batch in the then-latest HElib [@fhew]; and TFHE, working over the torus, cut the bootstrap to under a tenth of a second and shrank the bootstrapping key from about a gigabyte to twenty-four megabytes [@tfhe]. The last rung of this ladder is the scheme that will matter most.
The scheme of Cheon, Kim, Kim and Song that treats the LWE noise as part of an *approximation error*, so decryption returns the plaintext *plus a small, key-dependent error*. That trade makes real-number and complex arithmetic efficient -- ideal for encrypted machine learning -- and it is the scheme at the center of the break [@ckks].
Here is the toy version of the correctness cliff. Watch the noise compound until it crosses $q/2$ and the decryption flips from a clean answer to garbage. This is a caricature -- real noise growth is gentler than squaring -- but the shape is exactly right.
{`
// A ciphertext hides a message plus a small error term.
// Each homomorphic multiply compounds that error.
// Cross q/2 and decryption returns garbage -- a CORRECTNESS failure.
const q = 1 << 20; // ciphertext modulus
const half = q / 2; // decryption fails once noise passes this
let noise = 4; // a fresh ciphertext starts with small noise
const message = 7; // the value we are protecting
for (let mult = 1; mult <= 6; mult++) {
noise = noise * noise; // multiplication compounds noise fastest
const ok = noise < half;
const out = ok ? message : Math.floor(Math.random() * q);
console.log('after ' + mult + ' multiply(s): noise=' + noise +
(ok ? ' decrypts to ' + out : ' OVERFLOW -> garbage ' + out));
if (!ok) break;
}
// The key was never exposed. You just lost the answer.
`}
The point the demo makes is the one the field spent a decade internalizing and the public never did: crossing the noise ceiling costs you the *answer*, not the *key*. Nothing about an overflow reveals a secret. You recompute with bigger parameters and move on.
> **Note:** Spending the noise budget past $q/2$ yields a wrong answer -- garbage -- and nothing more. It is a **correctness** failure. The **security** consequence of noise arrives two sections from now, and from the opposite direction: not from noise that overflowed, but from residual noise you deliberately *revealed* by publishing a decryption. Overflow loses the answer; a released decryption can lose the key. Do not conflate them.
That reframe is the article's first genuine shift. You arrived believing the noise budget is FHE's fragile part, and that a secure base plus no overflow equals a safe system. Both halves are the wrong worry. The scheme families below all manage noise well enough to be useful; every one of them still has a primary fracture line, and not one of those fractures is an overflow.
| Scheme | Base assumption | Arithmetic | Noise control | Primary IND-CPA-D fracture |
|--------|-----------------|-----------|---------------|-----------------------------|
| CKKS | Ring-LWE | approximate real/complex | rescaling; modulus linear in depth | released approximate error is linear in the key [@limicciancio-21] |
| BGV | Ring-LWE | exact integer/modular | modulus switching; modulus ladder | decryption failures under heuristic correctness [@checri-crypto-24] |
| BFV | Ring-LWE | exact integer | scale-invariant; linear noise growth | decryption failures under heuristic correctness [@cheon-ccs-24] |
| TFHE / CGGI | torus (TLWE/TGLWE) | exact Boolean / small LUT | fast programmable bootstrapping | decryption failures under loose correctness [@cheon-ccs-24] |
Overflow only ruins an answer. The second debt is quieter and stranger: to compute forever, FHE must publish an encryption of its own secret key -- and simply hope that is safe.
## 5. The Debt Bootstrapping Silently Signs
Refreshing a ciphertext without exposing the key in the clear sounds impossible, and the way Gentry made it possible carries a hidden price. To run decryption homomorphically, the scheme needs the secret key *inside* the homomorphic computation. It cannot use the raw key -- that would defeat the purpose -- so it uses an *encryption* of the key, published as part of the evaluation material. Bootstrapping then evaluates "decrypt this ciphertext" under encryption, and out comes a fresh, low-noise ciphertext of the same value [@gentry-09].
Publishing an encryption of your own secret key is not something the base assumption ever promised was safe.
The assumption that a ciphertext encrypting the secret key itself stays secure -- that seeing an encryption of the key reveals nothing useful about the key. Bootstrapping requires it, and it does *not* follow from LWE or from plain IND-CPA security [@gentry-09].
Why does it not follow? Because ordinary security makes a promise only about messages an adversary chooses *without* knowing the key. The IND-CPA game, by construction, never lets the challenge plaintext depend on the secret. So it simply says nothing about what happens when you encrypt the key and hand it over. The gap is real, not pedantic.
In general, no. Chosen-plaintext security quantifies only over adversaries whose messages are independent of the key, so by definition it cannot constrain a ciphertext whose plaintext *is* the key. Cryptographers have exhibited schemes that are perfectly IND-CPA secure yet collapse the instant they encrypt their own secret key [@gkw-lwe-17]. That is why key-dependent-message security has to be assumed separately, or designed around -- it cannot be inherited for free from the base assumption.
So unbounded FHE runs on credit. Every bootstrap cashes a key-dependent-message assumption that no one has reduced to LWE, and Gentry flagged exactly this in 2009: whether FHE can be built from standard assumptions *without* circular security is an open problem, and it is still open [@gentry-09]. This is a place FHE could break with no attack on the lattice at all. If circular security turned out to be false for the deployed schemes, bootstrapping would leak -- and the floor would not have moved an inch.
There is one clean way out, and it is architectural rather than a fix.
Homomorphic encryption that evaluates circuits up to a pre-chosen depth $L$ *without* bootstrapping. Because it never publishes an encryption of the secret key, leveled FHE sidesteps the circular-security assumption entirely -- at the cost of giving up unbounded depth [@bgv].
BGV made this escape hatch practical: modulus switching controls noise well enough that a depth-$L$ circuit needs no refresh, so a large class of useful computations never signs the debt at all [@bgv]. The catch is in the definition -- once your circuit is deeper than the level budget you chose, you must bootstrap again, and the debt comes right back. Leveled FHE does not retire the assumption; it declines to take it on for bounded work.
flowchart TD
A["Noisy ciphertext near the budget ceiling"] --> B["Bootstrap runs decryption homomorphically"]
B --> C["Consumes the published encryption of the secret key"]
C --> D["Fresh low-noise ciphertext, keep computing"]
D --> A
C --> E["Debt: safety of publishing an encryption of the key is a circular / KDM assumption, not implied by LWE"]
A --> F["Leveled branch: cap depth at L, never bootstrap"]
F --> G["No published key-encryption, so no KDM debt"]
Gentry's original scheme also leaned on an *extra* sparse-subset-sum assumption from squashing, which Brakerski and Vaikuntanathan removed in 2011 [@bv11]. The field sheds assumptions when it can. It has not shed this one.
The noise is a correctness debt; circular security is an assumption debt. Neither is an attack. The cryptanalyst's breakthrough was to find a real one -- and it was hiding in the answers themselves.
## 6. The Cryptanalyst's Breakthrough: The IND-CPA-D Line
The wound was the celebrated feature. CKKS decryption returns the plaintext *plus* a small, key-dependent error, and that is precisely the trade that made encrypted machine learning practical -- you accept a little imprecision and you get real-number arithmetic that fits in a reasonable modulus [@ckks]. In 2021, Baiyu Li and Daniele Micciancio looked at that returned error and saw an oracle [@limicciancio-21].
To understand why, recall the bar every FHE scheme was measured against.
Indistinguishability under chosen-plaintext attack: no efficient adversary, given an *encryption* oracle, can tell apart encryptions of two plaintexts it chose. The adversary can encrypt anything, but it never sees a decryption [@limicciancio-21].
Read the last sentence again. The [IND-CPA game](/blog/secure-against-whom-the-security-definitions-every-protocol-/) never lets the adversary see a decrypted output. But seeing decrypted outputs is the entire point of FHE -- you compute on encrypted data *so that* you can publish the result. The security definition modeled a world that FHE deployments do not live in.
IND-CPA extended so the adversary also sees decryptions of ciphertexts whose plaintexts it is supposed to already know. This is the correct security bar for any scheme that releases computed results, and it is the bar CKKS failed [@limicciancio-21].
Under the decryption oracle, CKKS falls to a startlingly simple attack. Each released decryption is the plaintext plus an error, and that error is, in essence, a *linear function of the secret key*. The plaintext is known -- it is the answer to a computation the adversary requested on inputs it chose -- so subtracting it isolates a linear equation in the key.
One equation is not enough to pin down a key with thousands of coefficients. But CKKS is used to compute *many* results, and each one yields another equation. Collect enough, stack them into a linear system, and solve it with ordinary linear algebra. The key falls out [@limicciancio-21].
> **Key idea:** The correct answer is the attack. CKKS's own marketed output -- the decrypted mean, variance, or logistic fit -- is a linear function of the secret key. Nothing has to be "broken." The scheme hands you the equations, and you solve them.
The properties of this attack are what make it the article's cleanest evidence. It is **passive**: the adversary is honest-but-curious, requesting only the computations CKKS is normally used for and reading the outputs. It runs in **expected polynomial time** and recovers the *complete* secret key with high probability. And Li and Micciancio demonstrated it against four real libraries -- HEAAN, SEAL, HElib and PALISADE -- on exactly the workloads CKKS is sold for: means, variances, and Maclaurin-series approximations of logistic and exponential functions [@limicciancio-21].
sequenceDiagram
participant A as Adversary
participant O as CKKS evaluation and decryption oracle
participant S as Linear solver
A->>O: Request evaluations on known inputs
O-->>A: Return plaintext plus key-dependent error
A->>A: Treat each returned error as a linear equation in the key
A->>S: Stack enough equations into a linear system
S-->>A: Solve the system for the secret key
Note over A,S: Passive, expected polynomial time, no lattice solved
Here is the attack in miniature. The "leak" function stands in for a released CKKS decryption; the recovery is a few lines of Gaussian elimination with no libraries at all.
{`
# CKKS hands back plaintext + a small error that is linear in the secret key.
# Known plaintexts let the attacker isolate that error and solve for the key.
secret = [3.0, -5.0, 2.0] # the hidden key (attacker does not know this)
def leak(a):
# What a released CKKS decryption reveals: plaintext + dot(a, secret).
plaintext = 10.0
err = sum(ai * si for ai, si in zip(a, secret))
return plaintext, plaintext + err
# The attacker knows each plaintext and each public coefficient vector a.
rows = [[1.0, 0.0, 0.0], [1.0, 1.0, 0.0], [1.0, 1.0, 1.0]]
b = []
for a in rows:
p, dec = leak(a)
b.append(dec - p) # isolate dot(a, secret)
# Solve rows @ x = b by Gaussian elimination (no libraries needed).
M = [row[:] + [bi] for row, bi in zip(rows, b)]
n = len(M)
for i in range(n):
piv = M[i][i]
M[i] = [v / piv for v in M[i]]
for j in range(n):
if j != i:
f = M[j][i]
M[j] = [mj - f * mi for mj, mi in zip(M[j], M[i])]
recovered = [round(M[i][n], 6) for i in range(n)]
print("recovered key:", recovered) # -> [3.0, -5.0, 2.0]
`}
Standard IND-CPA security "does not adequately capture" the security of homomorphic encryption on approximate numbers: a passive adversary recovers the complete CKKS secret key in expected polynomial time [@limicciancio-21].
> **Note:** A raw CKKS output is not an inert answer. It is the plaintext plus an error term that is a linear equation in your secret key. Publish enough of them and you have published the key. If you take one operational rule from this article, it is this one [@limicciancio-21].
HEAAN, SEAL, HElib and PALISADE appear here as the places the attack *landed*, not as targets of a library audit. Which library did what belongs to the real-life sibling track; the point here is definitional [@limicciancio-21].
Name a disease and you invite a cure. The cure arrived -- and then it broke, and was re-patched, and broke again. That cycle is the state of the art.
## 7. Patch, Break, Re-Patch
The cure looks obvious. If a released decryption leaks the key-dependent error, drown that error in fresh noise before you publish. The story of why that obvious fix took four years, fell over in deployment, and is *still* being rewritten is the real state of the art.
Adding large fresh noise to a decryption before releasing it, so the key-dependent error is masked. The idea predates CKKS -- it comes from threshold FHE, where parties smudge their partial decryptions -- and it is provably safe only when the added noise is sized to the *worst case* [@ajw-11] [@lmss-22].
The first instinct was to size that noise cheaply -- to the *average* error a computation produces, or to a per-ciphertext estimate, or to sample it deterministically to save randomness. Every one of those shortcuts is provably insufficient. In 2022, Li, Micciancio, Schultz-Wu and Sorrell proved the surprising part: noise tuned even to a *dynamic, key-dependent* per-ciphertext estimate still leaks. The only thing that works is noise calibrated to the *worst-case* error growth of the computation, and they proved it with nearly matching upper and lower bounds -- you cannot do meaningfully better, and you cannot do meaningfully less [@lmss-22].
The same paper split bit-security into a *computational* parameter and a *statistical* one, which is what lets "how much noise is enough" be stated as a provable bound rather than a rule of thumb [@lmss-22].
That principled fix has a price. Worst-case noise costs real precision, and precision is the whole reason people reach for CKKS. So implementers did what the incentives pushed them toward: they reached for cheaper, average-case parameters. In 2024, Qian Guo, Denis Nabokov, Elias Suvanto and Thomas Johansson cashed that gap. Against non-worst-case flooding as configured in libraries, they achieved full key recovery from a *single* released decryption in OpenFHE, and they showed that generating the flooding noise deterministically is no defense at all [@guo-usenix-24].
"A single shared decryption can be enough for key recovery" against approximate FHE protected only by non-worst-case noise flooding, shown in practice on OpenFHE [@guo-usenix-24].
You can watch the gap with your own eyes. Flooding noise is zero-mean, so an attacker who collects enough decryptions can average it away -- unless the noise is large enough that a feasible number of queries cannot resolve the signal beneath it.
{`
import random
secret_bias = 0.75 # a key-dependent quantity the attacker wants
queries = 40000 # released decryptions the attacker averages over
def estimate(flood_bound):
total = 0.0
for _ in range(queries):
flood = random.uniform(-flood_bound, flood_bound) # zero-mean flooding
released = secret_bias + flood # what the attacker sees
total += released
return total / queries # averaging cancels the flood
avg_case = estimate(2.0) # flooding sized to typical error: too small
worst_case = estimate(20000.0) # flooding sized to worst-case sensitivity
print("average-case flooding -> attacker estimate:", round(avg_case, 3))
print("worst-case flooding -> attacker estimate:", round(worst_case, 1))
# Average-case flooding collapses to ~0.75: the secret leaks.
# Worst-case flooding keeps the estimate too noisy to read -- and the bound
# must grow with the number of queries, which is why the provable fixes
# either size to the worst case or make the noise query-count independent.
`}
The re-patch is where the field is now, and it is not a checkbox. Alexandru, Al Badawi, Micciancio and Polyakov argue the real gap is between the *application-agnostic* security definition and how libraries actually instantiate CKKS. Their application-aware homomorphic encryption supplies security definitions matched to a declared application, with a specification language, and a proof-of-concept in OpenFHE that counters the Guo attacks and also addresses the exact-scheme attacks of the same year [@aahe-24].
In 2025, Tabitha Ogilvie cut the *cost* of the provable fix. By treating CKKS rescaling noise as a linear "hint" on the secret and reducing to a HintLWE problem, she restores provable IND-CPA-D and key-recovery security with as little as about two bits of extra precision loss in rescale-dominated regimes, using a noise strategy independent of the number of oracle queries [@hintlwe-25].
flowchart LR
A["2021: IND-CPA-D break on CKKS"] --> B["2021 to 2022: heuristic noise flooding"]
B --> C["2022: LMSS worst-case DP flooding with matching bounds"]
C --> D["2024: Guo breaks non-worst-case flooding from a single decryption"]
D --> E["2024 to 2025: application-aware HE and HintLWE reduced noise"]
| Attack | Target | Leak mechanism | Attack cost | Data needed | Where it landed |
|--------|--------|----------------|-------------|-------------|-----------------|
| Li-Micciancio 2021 | CKKS | released key-dependent error | expected polynomial time | enough result pairs | HEAAN, SEAL, HElib, PALISADE [@limicciancio-21] |
| Guo et al. 2024 | CKKS, non-worst-case flooding | mis-sized flooding still leaks | practical | a single decryption | OpenFHE [@guo-usenix-24] |
| Checri / Cheon 2024 | exact BFV/BGV/TFHE, threshold | decryption failures | under an hour on a laptop | a few thousand ciphertexts | BFV in OpenFHE, CGGI simulated [@checri-crypto-24] [@cheon-ccs-24] |
| Defense | Year | Guarantee | Noise cost | Status against attacks |
|---------|------|-----------|-----------|------------------------|
| Heuristic flooding | 2021 | none | low | broken: one decryption suffices [@guo-usenix-24] |
| Worst-case DP flooding | 2022 | provable IND-CPA-D | high, at the lower bound | secure only if sized worst-case [@lmss-22] |
| Application-aware HE | 2024 | provable per application | model-level | counters Guo and the exact attacks [@aahe-24] |
| HintLWE reduced noise | 2025 | provable IND-CPA-D / KR-D | about two bits | counters passive key recovery [@hintlwe-25] |
Flooding fixes the *approximate* scheme. But in 2024 the ground moved under the schemes everyone thought were safe: the *exact* ones. They were supposed to be immune. They were not.
## 8. It Is Not Just Approximate: The Exact Schemes Fall Too
The comforting belief was that IND-CPA-D was CKKS's private problem. The *exact* schemes -- BGV, BFV, TFHE -- return the plaintext with no approximation error, so there is nothing key-dependent to leak. Li and Micciancio even proved that for exact schemes, ordinary IND-CPA security *does* imply IND-CPA-D security. The status quo looked safe on paper.
It looked safe because of a footnote. That equivalence holds only under *negligible* decryption failure -- the idealized assumption that an exact scheme essentially never returns a wrong value. Real implementations do not honor that assumption. They analyze correctness *heuristically* and tolerate noticeable decryption-failure probabilities, because tightening them costs performance. In 2024, two independent teams walked straight through that gap [@cheon-ccs-24] [@checri-crypto-24].
Cheon, Choe, Passelegue, Stehle and Suvanto exploited the imperfect correctness directly. Observing which ciphertexts decrypt incorrectly is itself information about the key, and they turned it into distinguishing and key-recovery attacks -- demonstrated on BFV in OpenFHE, simulated for CGGI in TFHE-rs, and extended to CKKS over discrete data and to threshold variants [@cheon-ccs-24].
Checri, Sirdey, Boudguiga and Bultel came at it from another direction: a CPA-D key-recovery attack on the linearly-homomorphic Regev cryptosystem that generalizes to BFV, BGV and TFHE, practical in under an hour on an average laptop, needing a few thousand ciphertexts and on the order of a million evaluations for full key recovery [@checri-crypto-24].
The two 2024 results share the decryption-oracle model with Li-Micciancio but leak through *different physics*, and holding that distinction is the whole point.
A single approximate-error repair -- flooding the released CKKS error -- cannot cover an exact-scheme leak that comes from decryption *failures*. Different cracks need different fixes, which is why "just flood everything" is not an answer here [@cheon-ccs-24].
flowchart TD
O["Decryption oracle: adversary sees results it can predict"] --> P1["Approximate path: CKKS returns plaintext plus a key-dependent error"]
O --> P2["Exact path: BGV, BFV and TFHE occasionally return a decryption failure"]
P1 --> R["Full secret-key recovery, no lattice solved"]
P2 --> R
| Dimension | Approximate (CKKS) | Exact (BGV / BFV / TFHE) |
|-----------|--------------------|---------------------------|
| Leak source | released approximate error | observed decryption failures |
| Trigger | any released decryption | heuristic correctness, noticeable failure rate |
| Where it landed | HEAAN, SEAL, HElib, PALISADE, OpenFHE [@limicciancio-21] | BFV in OpenFHE, CGGI in TFHE-rs simulated [@cheon-ccs-24] |
| Direct fix | worst-case noise flooding | tighten the failure probability; smudge threshold partials [@checri-crypto-24] |
| Same oracle model | yes | yes |
Threshold FHE is the sharpest edge of this. When decryption is distributed across parties, each party publishes a *partial* decryption, and that partial share carries key-dependent information all on its own.
This is the second level of the article's deepest shift. It was tempting to file the CKKS break under "approximate schemes are quirky" and assume a return to solid ground was one scheme away. Instead, both branches of FHE -- approximate and exact -- leak under a decryption oracle, through unrelated mechanisms. The problem was never one scheme's bug. It is a property of releasing results from a noisy system.
And yet none of this touched the lattice. Which raises the last scheme-layer question: how do we even *know* the lattice is safe? The answer is not a proof. It is a measurement.
## 9. The Parameter Line: Chosen Numbers Versus the Community Levels
Ask "is this deployment 128-bit secure?" and you are not invoking a theorem. You are asking whether someone picked the right numbers from a community table, computed by a piece of software that is revised every year. Security at this seam is a *measurement*, and measurements move.
The ruler has three parts. The Homomorphic Encryption Standard v1.1 fixes recommended Ring-LWE parameter tables for 128-, 192-, and 256-bit security [@he-standard-v11]. The 2024 Security Guidelines update those parameter sets and survey how open-source libraries actually select them [@security-guidelines-24]. Both are computed with the lattice-estimator, which runs the best known classical and quantum lattice-reduction models against candidate dimension, modulus, and error triples to output a concrete bit-security number [@aps-estimator]. A deployment is only ever as safe as the parameters someone actually selected from that ruler.
That creates three structural failure modes, all distinct from a library bug. The first is *estimator drift*: today's "128-bit" is the output of today's best attacks, and it erodes as lattice reduction improves.
The lattice-estimator carries its own disclaimer that concrete hardness is a moving target. That is exactly why drift is a *structural* failure mode and not a coding mistake -- the number is designed to change [@aps-estimator].
The second is *stale tables*: parameter sets copied from an old paper or an old library default, never re-checked against the current estimator. The third is the simplest and the most dangerous: parameters chosen, whether by error or by optimism, that sit below the security level they are advertised to meet. None of these is exotic. All of them silently under-secure a system whose users believe a specific number.
There is a naming trap here that this article has to defuse, because getting it wrong would overstate FHE's assurance.
> **Note:** The 128-, 192-, and 256-bit levels are a *de facto community* standard: the Homomorphic Encryption Standard and the 2024 Security Guidelines. There is no ISO/IEC- or NIST-blessed FHE *security level*. An ISO/IEC standardization effort is described only as upcoming and is unpublished, so no document number should be attached to it. Read "128-bit FHE" as "computed against the current community table," never as an ISO guarantee [@security-guidelines-24] [@he-standard-v11].
| Element | What it is | Structural failure mode |
|---------|-----------|--------------------------|
| Target levels | 128/192/256-bit tables in the HE Standard v1.1 | copied or outdated parameter sets [@he-standard-v11] |
| The estimator | lattice-estimator: concrete bit-security against lattice reduction | estimator drift as attacks improve [@aps-estimator] |
| The 2024 guidelines | updated parameter sets and a library-selection survey | parameters chosen below the advertised level [@security-guidelines-24] |
| Standardization status | community standard; ISO/IEC upcoming and unpublished | implying an ISO- or NIST-blessed level exists [@security-guidelines-24] |
This seam fails gradually and quietly rather than catastrophically, but it is still a scheme-layer failure: it is about the numbers a deployment chose against a moving table, not about the lattice problem itself being weak. Every seam so far is a place FHE breaks *first*. There is exactly one break that would take *everything* at once -- and the most important thing about it is that it is not here yet.
## 10. The One Break That Would Take Everything
There is exactly one way FHE breaks all at once, and it is at the floor, not a seam: an efficient algorithm for Ring-LWE or Module-LWE. Such a solver would collapse every lattice-based FHE scheme at the foundation, and it would take [ML-KEM](/blog/two-standards-one-lattice-how-ml-kem-and-ml-dsa-would-break/) down with it, because they rest on the same family of assumptions [@lpr-rlwe]. It is a genuinely structural single point of failure -- and it is also the one break for which there is no evidence at all.
Start with the fear most people carry: a [quantum computer](/blog/how-q-day-breaks-everything-shors-algorithm-and-the-simultan/). It is misplaced here, and the reason is precise.
> **Note:** Shor's algorithm breaks factoring and discrete logarithms because those are abelian hidden-subgroup problems with the exact structure Shor exploits. Lattice problems do not have that structure, so Shor does not apply to them. The other quantum tool, Grover's search, buys only a generic square-root speedup -- a discount already accounted for in the parameter tables. This is why "FHE is post-quantum" is a claim about the floor, not the seams [@regev-lwe] [@peikert-survey].
There is a beautiful twist buried in the foundations. Regev's original hardness argument for LWE is itself a *quantum* reduction: it shows that solving average-case LWE would let a *quantum* algorithm solve worst-case lattice problems [@regev-lwe]. The post-quantum confidence in FHE does not come from ignoring quantum computers; it comes from a hardness argument that already has one built in, surveyed and reinforced across a decade of lattice cryptography [@peikert-survey]. And after all of it, no efficient solver -- quantum or classical -- is known.
Now the deeper ceiling, the one that does not go away even if the lattice never falls: *no FHE assumption is proven hard.* This is not a gap waiting to be filled. The decision lattice problems underlying Ring-LWE, such as approximating the shortest vector within a $\sqrt{n}$ factor, sit in $\mathrm{NP} \cap \mathrm{coNP}$ [@aharonov-regev].
Membership in $\mathrm{NP} \cap \mathrm{coNP}$ buys a *ceiling*, not a *floor*. It tells you the problem is almost certainly not NP-complete, so hardness cannot be inherited from the hardest problems in NP. It does not tell you the problem is hard. Both facts point the same way: FHE security is an assumption, permanently [@aharonov-regev].
A problem in $\mathrm{NP} \cap \mathrm{coNP}$ cannot be NP-complete unless the polynomial hierarchy collapses, an outcome complexity theorists treat as effectively impossible. So the hardness that FHE rests on can never be a theorem derived from NP-completeness. It is *necessarily* an assumption. That is not a special weakness of FHE -- it is the same epistemic position every public-key cryptosystem occupies. FHE simply occupies it on a younger, less-tested foundation, and openly.
It is worth noting that FHE does not *have* to be lattice-based in principle. An early scheme built FHE over the integers, reducing to an approximate-greatest-common-divisor assumption rather than lattices, which proved the concept was not tied to lattices -- but its impractical key sizes left it a curiosity, and no practical FHE lives outside the Ring-LWE, Module-LWE, and torus families today [@dghv-09]. The single point of failure is real precisely because the practical schemes all share it.
So the theoretical picture resolves into two very different kinds of risk. The base lattice is a *catastrophic-but-hypothetical* failure: if it fell, everything falls, but nothing suggests it will, and Shor cannot reach it. The scheme layer is a *likely-and-practical* failure: it has cracked repeatedly, along four separate seams, every crack demonstrated, none of them touching the floor. Weigh those against each other and the thesis stops being a claim and becomes an accounting.
Now the argument can be settled. Line up every fracture line, rank it by how it fails and how likely that is, and the pattern is unmistakable.
## 11. Where It Would Break First
The thesis has been earned section by section. Now it collapses into a single table you can read down one column to see the whole argument. Each row is a fracture line this article walked; the columns are how it fails, what *kind* of claim its failure is, how likely it is, and what it costs.
| Fracture line | Mechanism | Epistemic class | Likelihood | Cost of failure |
|---------------|-----------|-----------------|-----------|-----------------|
| Noise / correctness overflow | error crosses $q/2$ | engineering | common, but not a key leak | a wrong answer [@gentry-09] |
| Circular-security / KDM debt | bootstrapping publishes an encryption of the key | assumption | no known attack | catastrophic if the assumption is false [@gentry-09] |
| IND-CPA-D on approximate CKKS | released error is linear in the key | definition | demonstrated | full key recovery [@limicciancio-21] |
| IND-CPA-D on exact and threshold | decryption failures under loose correctness | definition / correctness | demonstrated in 2024 | full key recovery [@checri-crypto-24] |
| Parameter versus level drift | estimator movement, stale tables | measurement | gradual | silent under-security [@security-guidelines-24] |
| Base-lattice solver | efficient quantum or classical Ring-LWE break | hypothetical | no known attack | everything [@regev-lwe] |
Read down the *epistemic class* column and the shape of the argument appears. Five of the six rows are scheme-layer: an engineering limit, an unproven assumption, two definitional breaks, and a measurement that drifts. Four of those five are either demonstrated in practice or a live assumption every bootstrap depends on. Only the last row, the lattice, is purely hypothetical -- and it is the only row whose cost is the entire word "everything."
> **Key idea:** The likeliest failures are all in the scheme layer -- noise, the KDM assumption, the two IND-CPA-D breaks, and parameter drift. The base lattice is the lone catastrophic-but-hypothetical outlier: the highest cost, the lowest evidence it will ever be paid.
That distribution is not a coincidence to be explained away; it *is* the argument. If FHE's real risk lived in the lattice, the table would be top-heavy with hypothetical rows and the demonstrated attacks would be lattice reductions. Instead the demonstrated attacks are a linear solve on a released error, a mis-sized noise mask, and a heuristic decryption-failure rate. Every one of them lives above the floor.
Not one of these breaks solved a lattice. Every one of them lived in the machinery above it.
There is one honest caveat that keeps "likeliest" a probabilistic claim rather than an absolute one. The base-lattice row has the lowest probability *and* the highest cost, so it is never something to ignore -- a low-probability, total-loss event still deserves conservative margins. The thesis is not that the lattice is safe forever. It is that, on every piece of evidence available today, FHE would break in the scheme layer first, and by a wide margin.
A verdict is only useful if it tells you what to do. This one does -- item by item.
## 12. How Not to Be the Break
Every fracture line in this article is also an instruction. Here is the checklist a team shipping FHE in 2026 can act on, each item pointing back to the section that earned it.
Start with the single rule that prevents the centerpiece attack.
> **Note:** A released decryption is an oracle. Flood it to the worst case, or do not release it. Everything else on this list is a refinement of that sentence [@limicciancio-21] [@lmss-22].
If you use CKKS for analytics or machine learning and you will release results, never publish a raw decryption; add noise flooding sized to the *worst-case* error growth, or use an application-aware configuration, and prefer HintLWE-grade noise where your library supports it [@lmss-22] [@aahe-24] [@hintlwe-25]. Treat every value you release as a partial oracle on the key, not as an inert answer. Average-case flooding is not a lighter version of the fix; it is the thing Guo and colleagues broke from a single decryption [@guo-usenix-24].
If you use an exact scheme -- BGV, BFV, or TFHE -- do not rely on the folklore that exact means immune. Enforce a *negligible* decryption-failure probability rather than a heuristic average, and if outputs are released under an oracle, treat the scheme as CPA-D-exposed and smudge accordingly [@cheon-ccs-24]. In any threshold or multi-party protocol, add smudging noise *after* each partial decryption, before shares are combined [@checri-crypto-24].
Where your computation has bounded depth, choose *leveled* parameters and skip bootstrapping entirely -- that dodges the circular-security assumption at no extra cost [@bgv]. Select lattice parameters from the *current* estimator and re-check them against the 2024 Security Guidelines rather than copying a table from an old paper [@aps-estimator] [@security-guidelines-24].
Crypto-agility means being able to swap parameters or schemes without re-architecting, so a future estimator revision -- or, in the worst case, a lattice advance -- is a configuration change, not a rebuild.
And for the floor itself, hold conservative margins and keep the deployment [crypto-agile](/blog/you-cannot-rotate-what-you-cannot-see-crypto-agility-and-the/). The base-lattice break is unlikely, but its cost is total, and margins plus agility are how you price a low-probability, total-loss risk.
| Fracture line | What to do | Where it was earned |
|---------------|-----------|---------------------|
| CKKS output leak | never release raw decryptions; flood to worst-case | Sections 6 and 7 [@limicciancio-21] [@lmss-22] |
| Non-worst-case flooding | size flooding to worst-case, or use an application-aware config | Section 7 [@guo-usenix-24] [@aahe-24] |
| Exact-scheme failures | enforce negligible decryption-failure probability | Section 8 [@cheon-ccs-24] |
| Threshold partial decryption | smudge after each partial decryption | Section 8 [@checri-crypto-24] |
| Circular-security debt | prefer leveled parameters when depth allows | Section 5 [@bgv] |
| Parameter drift | select from the current estimator; re-check the guidelines | Section 9 [@aps-estimator] [@security-guidelines-24] |
| Base lattice | conservative margins and crypto-agility | Section 10 [@regev-lwe] |
The misconceptions this topic breeds deserve a direct answer -- so we end by naming them.
## 13. The Misconceptions This Topic Breeds
This topic breeds a predictable set of misreadings, and each one, answered honestly, restates the thesis from a different angle.
No. The breaks in this article are *definitional* and *parameter* breaks, and each has a repair -- worst-case flooding, application-aware configurations, tightened correctness [@limicciancio-21] [@aahe-24]. No strong, correctly parameterized, correctly used FHE deployment has fallen. The right reading is not "FHE is broken" but "FHE breaks in specific, understood, fixable places -- all above the lattice."
Not by any known attack. Shor's algorithm does not apply to lattice problems, and Grover offers only a square-root speedup already priced into the parameters [@regev-lwe] [@peikert-survey]. If a quantum solver for Ring-LWE ever appeared, it would break the *lattice* -- the floor shared with ML-KEM -- not the scheme layer this article is about.
No. CKKS remains the practical choice for encrypted real-number analytics, but you must never publish a raw decryption and must flood released results to the worst case [@limicciancio-21] [@lmss-22]. The lesson is operational, not a retirement notice: released decryptions are oracles, so treat them like oracles.
No, not since 2024. Exact and threshold schemes leak through *decryption failures* under the heuristic correctness that deployments tolerate for speed -- a different mechanism from CKKS, but the same decryption-oracle model [@cheon-ccs-24] [@checri-crypto-24]. Immunity was a footnote assumption that real implementations quietly violate.
Not yet. The 128-, 192-, and 256-bit levels come from a *de facto community* standard -- the Homomorphic Encryption Standard and the 2024 Security Guidelines -- computed by the lattice-estimator [@he-standard-v11] [@security-guidelines-24]. An ISO/IEC effort is described only as upcoming and is unpublished, so "128-bit FHE" is a measurement against a community table, not an ISO or NIST guarantee.
Only if the circular-security assumption is false. Bootstrapping publishes an encryption of the secret key, which requires key-dependent-message security that LWE does not imply -- but no known attack exploits it, and *leveled* FHE avoids the assumption entirely by capping depth [@gentry-09] [@bgv]. It is a live assumption, not a demonstrated break.
No. Overflow is a *correctness* failure: you get a garbage answer, and the key is never exposed [@gentry-09]. Do not conflate it with the IND-CPA-D key leak, which comes from *revealing* a decryption, not from noise crossing the ceiling. They are different fracture lines with different fixes.
The floor holds; the seams leak. Fifteen years of FHE show a base lattice that has never fallen and a scheme layer that has cracked along four seams -- the noise budget, the circular-security debt, the IND-CPA-D line, and parameter drift -- every crack demonstrated or assumed, none of them touching the floor. The purest of them is the one that still feels impossible: the *correct* answer you are allowed to publish is the equation that gives back the key.
Two siblings finish the picture. "Never Decrypted: FHE" is the constructive story -- how you actually compute on ciphertext, and what it costs. "Two Standards, One Lattice" is the floor itself -- the assumption FHE shares with the post-quantum standard ML-KEM.
The repair arc that runs through this article is not a closed chapter; it is a discipline still being written, one attack and one re-patch at a time. The most useful thing you can carry out of it is a habit: when an FHE system hands you an answer, ask not whether the lattice is safe, but what you just revealed by reading it.