Computing Without Decrypting: Fully Homomorphic Encryption from Gentry's Bootstrapping to a Draft ISO Standard

The Hook: A Question That Went Unanswered for 31 Years

In 1978, three people at MIT asked a question that sounds so naive you might take it for trivial. Ronald L. Rivest, Len Adleman and Michael L. Dertouzos wrote a paper titled On Data Banks and Privacy Homomorphisms. Their example is remarkably mundane: a small loan company stores its records with a commercial time-sharing service. The records are confidential. You could store them encrypted — but then the service cannot compute anything with them. Decrypt them for processing, and it sees everything.

Their question was: are there encryption functions that let you compute on the ciphertext without decrypting it? They called such functions privacy homomorphisms — verbatim: "These special encryption functions we call 'privacy homomorphisms'; they form an interesting subset of arbitrary encryption schemes." If the service provider could derive the ciphertext of a + b from the ciphertexts of a and b without ever seeing a plaintext, the dilemma would dissolve.

The paper gave sample constructions — the text says four ("We give here four sample privacy homomorphisms."), while Examples 1 through 5 are numbered. The inconsistency has been in the paper since 1978. More telling than the count is the authors' honesty about their own material. Verbatim: "Some of them are rather weak cryptographically; a 'chosen plain-text attack' may break them." Example 4 is explicitly described as "not really secure against a 'chosen plaintext attack', although it has many good properties otherwise".

And they noted a limit of their own constructions that anticipates today's model: it is "not possible to simultaneously preserve security and give the system the operation of performing comparisons … against known constants". The reasoning is in the paper itself — anyone who can read off comparisons against constants in the clear can run a binary search and thereby extract any value. What matters is what this does not mean: comparisons can perfectly well be computed homomorphically, and today's schemes do so via look-up tables. Their result simply stays encrypted. That is exactly where the circuit model comes from — the model that explains the costs in Part 5.

So the question was out there — and stayed out there. Schemes with one homomorphic operation existed: RSA is multiplicatively homomorphic, Paillier additively. But a scheme allowing both operations arbitrarily often, and thus able to evaluate any computable function on encrypted data, was missing for 31 years. In 2009, Craig Gentry wrote the sentence cryptography had waited thirty-one years for, in the abstract of his Stanford dissertation: "We propose the first fully homomorphic encryption scheme, solving a central open problem in cryptography." And he attributed it directly: "This problem was posed by Rivest et al. in 1978."

This article takes that apart: why it took so long, what Gentry's trick consists of — and which unproven assumption it carries with it — how today's scheme families differ and how the ISO series cuts across them, what the whole thing costs in computation time, where an unpleasant surprise lay in wait in 2021 and again in 2024, and what fully homomorphic encryption explicitly does not deliver. The last of these is the most important part.

Part 1: Why It Took 31 Years – The Noise Problem

The modern answer to the 1978 question comes from lattice theory, and it brings a price with it that shapes the entire engineering of the field.

Learning with Errors

Oded Regev published his results in 2005; the version used here, dated 2 May 2009, carries the title On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. The central problem — Learning With Errors, or LWE — can be described in one sentence: you are given pairs (a_i, b_i), where a_i is drawn independently and uniformly from Z_p^n and b_i = ⟨s, a_i⟩ + e_i. Each error term e_i ∈ Z_p is drawn independently from an error distribution χ. The task is to recover the secret vector s.

Without the error terms, this is linear algebra and solved in seconds. With them, it is considered hard. Regev describes it in the paper as "a natural extension of the 'learning from parity with error' problem to higher moduli" and likewise: "It can also be viewed as the problem of decoding from a random linear code."

His main theorem (Theorem 1.1, informal version) states: for n, p and α ∈ (0,1) with αp > 2√n, anyone who solves LWE efficiently thereby yields "an efficient quantum algorithm that approximates the decision version of the shortest vector problem (GAPSVP) and the shortest independent vectors problem (SIVP) to within Õ(n/α) in the worst case".

The word quantum here is not marketing but a limitation of the proof. Regev writes explicitly: "Our reduction, however, is quantum." And in the abstract: "A main open question is whether this reduction can be made classical (i.e., non-quantum)." In the section on open questions he accordingly states that the main open question raised by the work is whether Theorem 1.1 can be "dequantized".

The Noise Is Both Protection and Problem

For cryptography, the noise is the actual protective mechanism: it makes the ciphertext indistinguishable from a random string. For computing on ciphertexts, it is the curse. Add two ciphertexts and the error terms add. Multiply them and the errors multiply — the noise grows considerably faster. At some point it crosses a threshold beyond which decryption no longer yields the correct plaintext but garbage.

That makes it clear why partial successes were possible but a complete one was not: you could build schemes that tolerate a bounded number of operations — "somewhat homomorphic". The multiplicative depth such a scheme can withstand is the so-called noise budget. Once exhausted, the ciphertext is lost. An arbitrary function cannot be evaluated this way, because you do not want to bound the depth of the circuit in advance.

This noise will follow us through the whole article. It disappears in none of today's schemes — it is merely accounted for differently. And in Part 6 it turns from a technical detail into an attack vector.

Part 2: Gentry's Trick – Decrypting Without Decrypting

Gentry's solution is one of the most elegant arguments in recent cryptography, and it consists of inverting the problem.

Bootstrapping

The idea: if the noise is the problem, then I need an operation that resets it — a way of refreshing the ciphertext. Decrypting and re-encrypting would do that, but the server does not have the secret key; if it did, the entire scheme would be pointless.

Gentry's way out: you run the decryption function itself homomorphically. The server is given an encryption of the secret key and uses it to evaluate the decryption circuit on the noisy ciphertext. The result is a ciphertext of the same plaintext — carrying the noise produced by homomorphically evaluating the decryption circuit, instead of the accumulated noise of the computation so far. In Gentry's words from the dissertation: "This is the idea behind bootstrapping: we do decrypt the ciphertext, but homomorphically!"

From this follows his general result, and it is a pure self-reference argument. It suffices to build a scheme that can evaluate its own — slightly augmented — decryption circuit; Gentry calls such a scheme bootstrappable.

A caveat belongs here, however, one that is almost always missing from popular accounts. Bootstrappability yields only leveled FHE at first — via a chain of L key pairs, where each refresh moves on to the next key. Unbounded depth with a single key pair follows only under an additional assumption: circular security, that is, the assumption that the encryption of the secret key under its own public key is secure. This assumption is not proven from any standard problem. How fundamental it is becomes clear from a 2014 paper by Canetti, Lin, Tessaro and Vaikuntanathan, which describes its own result as "the first construction of full-fledged FHE that does not rely on encryption with circular security" — implying that every bootstrapping-based full FHE construction before it relied on exactly that. Every practically deployed FHE scheme with unbounded depth therefore rests on an assumption for which there is no hardness proof.

Squashing: The Encrypter Starts the Decryption

The catch: Gentry's first scheme, based on ideal lattices, was not bootstrappable, and the reason is subtler than it is usually rendered. The depth the scheme can correctly evaluate depends doubly logarithmically on the noise radii (in the dissertation: log log r_Dec − log log(γ_Mult(R) · r_Enc)). The depth of its own decryption circuit, by contrast, additionally contains a term logarithmic in the lattice dimension n (O(log n + log log r_Dec)). It is precisely this log n term that makes the scheme fall just short of reaching itself — and Gentry frames this as an observation, not a proof: "for this initial scheme, it seems that no matter how the parameters are set, the decryption circuit is always slightly too complex for the scheme to evaluate."

The final step of the construction is squashing: the decryption circuit is made shallower. Gentry states the goal as reducing decryption complexity "without affecting the 'evaluative capacity' of the scheme at all" — while conceding a very slight loss for one intermediate step. Technically, one places a "hint" about the secret key into the public key. This hint is not enough to decrypt a ciphertext, but it allows the ciphertext to be preprocessed so that a very shallow circuit can decrypt it. In the abstract of his conference talk, Gentry describes the principle vividly: you put the encrypter in a position to start the decryption and leave the decrypter less work — much as in a server-aided cryptosystem. This requires a second hardness assumption: "we require a second computational hardness assumption."

The conference version appeared in 2009 under the title Fully Homomorphic Encryption Using Ideal Lattices at the Annual ACM SIGACT Symposium on Theory of Computing (STOC 2009); the detailed treatment is the Stanford dissertation A Fully Homomorphic Encryption Scheme of September 2009.

What Bootstrapping Is Not: An Efficiency Gain

Bootstrapping is the lever for unbounded depth, not for speed. It is the most expensive single operation in the field, and a large part of the research since 2009 consists of either avoiding it or making it cheaper. Both routes were taken.

Part 3: Avoid or Accelerate – The Two Lines of Development

The Avoidance Path: Leveled FHE

In 2011, Zvika Brakerski, Craig Gentry and Vinod Vaikuntanathan showed in Fully Homomorphic Encryption without Bootstrapping (the scheme is known today as BGV) that bootstrapping is not needed for many purposes. Their scheme evaluates circuits with L levels at a per-gate cost of "Õ(λ · L³) per-gate computation" — quasi-linear in the security parameter λ. Security rests "on RLWE for an approximation factor exponential in L".

The price is in the word leveled: the circuit depth L must be fixed in advance, because the parameters depend on it. That is not a side condition but the boundary of the approach. BGV consistently treats bootstrapping as an optimization, not a foundation: with bootstrapping, the per-gate cost drops to Õ(λ²), independent of L — though security then rests on RLWE for quasi-polynomial factors, that is, on a strengthened assumption. For circuits of large width — in the abstract: "for circuits of large width — e.g., where a constant fraction of levels have width at least λ" — this can be reduced to Õ(λ) by batching the bootstrapping. This last bound applies explicitly only to wide circuits and is not the scheme's general figure of merit.

For unbounded depth, bootstrapping is the only means known from lattice assumptions. The impossibility of other routes, however, is not proven: from sub-exponentially hard indistinguishability obfuscation, as the 2014 paper cited above shows, non-leveled FHE can be constructed even without a circularity assumption — albeit from an assumption that is not practically usable. Bootstrapping is thus "indispensable" in practice, not as a theorem.

The Acceleration Path: TFHE

The other line optimized bootstrapping so far that it became the standard operation. Ilaria Chillotti, Nicolas Gama, Mariya Georgieva and Malika Izabachène presented TFHE: Fast Fully Homomorphic Encryption over the Torus, the full version of their Asiacrypt 2016 and Asiacrypt 2017 papers (Journal of Cryptology, 2019). The numbers in the abstract explain the scheme's popularity: the bootstrapping running time of the predecessor scheme FHEW drops "from 690ms to 13ms single core", at the same security parameter — and with a bootstrapping key of 16 MB instead of 1 GB. Added to this is a new circuit bootstrapping that converts LWE ciphertexts into low-noise RingGSW ciphertexts "in just 137ms".

The mode in which TFHE is usually operated is called gate bootstrapping: each binary gate is concluded with its own bootstrapping, so the noise never grows. This is computationally wasteful — but it makes the circuit depth irrelevant, and in practice that is often worth more than a smaller constant factor.

Part 4: Three Computational Models, Four Schemes – and a Standards Series That Follows Them

Anyone deploying FHE today chooses not "FHE" but one of a few families with different computational models. I am of the opinion that this distinction is skipped too often in discussion — that cannot be substantiated, but the distinction decides whether a project works technically at all.

Exact Arithmetic on Modular Integers: BGV and BFV

BGV and BFV compute exactly with integers modulo a plaintext modulus. They support batching: a plaintext polynomial encodes a vector of values, and one homomorphic operation acts on all slots at once (SIMD). For statistics, database queries and anything where a rounding error is unacceptable, they are the choice. According to Apple's implementation, BFV rests "on the ring learning with errors (RLWE) hardness problem, which is quantum resistant".

Approximate Arithmetic: CKKS

In 2017, Jung Hee Cheon, Andrey Kim, Miran Kim and Yongsoo Song published the CKKS scheme at ASIACRYPT (Homomorphic Encryption for Arithmetic of Approximate Numbers). The idea is a deliberate reframing: instead of fighting the noise as an error, it is treated as part of the rounding error that approximate arithmetic produces anyway. The paper describes a new rescaling procedure that "truncates a ciphertext into a smaller modulus, which leads to rounding of plaintext"; the noise is scaled down along with the plaintext. Decryption "outputs an approximate value of plaintext with the predetermined precision".

The remarkable sentence in the abstract is this: the precision loss during evaluation is bounded by the depth of the circuit, and "it is at most one more bit compared with unencrypted approximate arithmetic such as floating-point operations". In exchange, the bit size of the ciphertext modulus grows linearly with the circuit depth, precisely because of the rescaling. As applications, the paper names the multiplicative inverse, the exponential and logistic functions, and the discrete Fourier transform.

Important for understanding the later attack: the noise does not disappear in CKKS, it is merely accounted for differently. It costs precision instead of correctness, and it still bounds the depth — the ciphertext modulus growing linearly with depth is exactly that bound. And it is precisely this accounted-for residual noise that becomes the attack vector in 2021.

This makes CKKS the obvious scheme for the arithmetic part of machine learning on encrypted data — inner products, polynomial approximations. For comparisons, maxima and non-polynomial activation functions it is the wrong choice.

Evaluation via Look-up Tables: TFHE/FHEW

The third family does not compute arithmetically but evaluates functions via look-up tables. According to its abstract, TFHE explicitly optimizes "the evaluation of look-up tables and arbitrary functions in RingGSW based homomorphic schemes". This is the route for everything arithmetically awkward — comparisons, maxima, activation functions, bit operations.

The ISO Series Is Organized by Computational Model, Not by Scheme

At ISO/IEC JTC 1/SC 27 (Information security, cybersecurity and privacy protection), the standards series ISO/IEC 28033 Information security — Fully homomorphic encryption is under development. Its mechanism parts are cut not by scheme but by computational model:

Three points of interpretation. First: the "plausible mapping" column is a reading, not a determination by the standard — the titles of the parts name no schemes. Four schemes distribute across three mechanism parts, because BGV and BFV fall into one part.

Second, and this is the most important point for practice: none of the parts is a published International Standard as of retrieval. All four mechanism parts carry the status "Under development"; Parts 1 and 2 stand as Draft International Standards at the close of voting, Parts 3 and 4 as Final Drafts in the approval phase. Anyone who today demands or promises conformance "to ISO 28033" is referring to a draft.

Third: the existence of a separate Part 5 for scheme switching shows that the standardization effort has real pipelines in view — practical applications move between exact arithmetic, approximate arithmetic and table evaluation. The idea is not new: the CHIMERA paper by Boura, Gama, Georgieva and Jetchev from 2018 names "the recent standardization initiatives of homomorphic schemes and common APIs" explicitly as its motivation, and justifies scheme switching on the grounds that "operations of different nature and not achievable within a single FHE scheme have to be performed". What remains to be noted is that this switch is itself a cryptographic procedure with costs of its own.

Part 5: What It Costs – and Why the Factor Is Only Half the Answer

The Order of Magnitude

With the DPRIVE program (Data Protection in Virtual Environments), DARPA addressed exactly this point. On the program page — now marked "This program is now complete" — stands the diagnosis: FHE "requires enormous computation time to perform even simple operations", and "running FHE in software on standard processing hardware remains untenable for practical data security applications due to the massive processing overhead". The program goal is stated with a number: FHE computation "within a factor of ten of unencrypted computations", elsewhere "within one order of magnitude of current performance on unencrypted data". The accelerator was to reduce the run-time overhead relative to software-based FHE on conventional CPUs "by many orders of magnitude" — so that phrase denotes the required reduction, not the current state.

The current state is not given on the program page. A measured, citable benchmark nonetheless exists. In their MICRO 2021 paper on the FHE accelerator F1, Samardzic, Feldmann, Krastev, Devadas, Dreslinski, Peikert and Sanchez put the gap between carefully optimized software FHE and plaintext computation at "10,000× to 100,000× slower than unencrypted computation when executed in carefully optimized software", in the abstract as "4 to 5 orders of magnitude". For comparison, the same paper cites "about 10^9 times slower" for the earliest schemes of 2009. That is a characterization of the field, not a single measurement — what the paper itself measures is the F1 accelerator against software FHE on a quad-core Xeon, with factors from 1,195x (CKKS bootstrapping) to 17,412x (LoLa-MNIST), geometric mean 5,432x. Noteworthy is the methodological caveat reported there: microbenchmarks yield far higher speedups (up to 48,640x) than full benchmarks, because they are "pure compute" and "miss FHE's data-movement bottlenecks".

On the software side, OpenFHE is the implementation with the broadest scheme coverage; its paper (WAHC 2022, 23 authors, including Halevi, Micciancio, Polyakov, Rohloff and Vaikuntanathan) states for the FHEW/TFHE-style schemes DM, CGGI and LMKCDEY, in which non-linear operations run via functional bootstrapping, "a form of fast functional bootstrapping (under 100 ms)" — the figure appears in the body text, not in the abstract. The comparison figures given there are relative costs between FHE configurations, typically factors of 1.2 to 1.5 between different modes, not comparisons against plaintext computation.

The Shape of the Computation

The practically more important consequence is not the factor but the form into which a computation must be cast. Because the evaluator sees no plaintext, it cannot branch on plaintext values: a condition over encrypted data has no result it could read. That is why the scheme papers — Gentry, BGV, TFHE, CKKS — formulate the model as the evaluation of circuits.

Concretely, that means: an if becomes both branches plus an arithmetic selection; a loop must be unrolled to its maximum iteration count in the circuit model; a database access via an encrypted index becomes, in every system deployed today, a pass over all entries.

That this is not necessarily so belongs to an honest account — and it is more surprising than practice would suggest. In How to Run Turing Machines on Encrypted Data (CRYPTO 2013), Goldwasser, Kalai, Popa and Vaikuntanathan identify exactly this drawback as remediable: the shortcoming of the circuit model is that "evaluating an algorithm over encrypted data is as slow as the worst-case running time of that algorithm"; their variant runs "in time that is dependent on the running time of M on input x". The price is that the actual running time leaks as side information. And Lin, Mook and Wichs show in Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE (CRYPTO 2023) that after a preprocessing of O(N^(1+ε)) a server can answer each query "in time that is sub-linear in the database size", with polylogarithmic running time and communication — and they construct RAM-FHE "under the RingLWE assumption with circular security", whose costs depend on the RAM running time rather than the circuit size. Both are asymptotic and without practical implementation; the sentence "FHE always has to touch everything" is thus a statement about the state of the art, not about the theory.

The overhead of FHE is therefore not only cryptography: added to it is the loss of all the shortcuts normal programs take. How large that share is, the literature does not quantify; what is measured is dominated by data movement and bootstrapping — one accelerator-design paper budgets "more than 50% of the total compute and memory budget" for bootstrapping.

Part 6: The CKKS Case – When the Security Definition Itself Became the Gap

This is the most instructive incident in the history of the field that I know of, and it is not about an implementation bug but about a definition.

CKKS was designed to be IND-CPA secure under the classical definition and was deployed as such for years. In 2021, Baiyu Li and Daniele Micciancio presented the paper On the Security of Homomorphic Encryption on Approximate Numbers at EUROCRYPT — and in it, passive attacks on CKKS that lead to complete key recovery: "leading to complete key recovery with high probability and very modest running times", in expected polynomial time. The authors implemented the attack and tested it against the major open-source libraries, including HEAAN, SEAL, HElib and PALISADE. The functions evaluated were not laboratory constructs but exactly what CKKS is used for: "mean and variance computations, and approximation of logistic and exponential functions using their Maclaurin series".

How the Attack Actually Works

The obvious explanation — "the residual noise depends on the key, so it reveals it" — is wrong. The mechanism is exactly the reverse, and that is what makes it so striking. Knowledge of the decryption result eliminates the noise:

1. A ciphertext is a pair (a, b) with b = ⟨s, a⟩ + m + e.
2. Decryption yields m + e — with an approximate scheme, precisely not just m. The identity function suffices for this; nothing needs to be evaluated at all.
3. The attacker computes c = b − (m + e). The unknown error e cancels. What remains is c = ⟨s, a⟩ mod q — an error-free linear equation in the unknowns of the key.
4. The hard RLWE problem is thereby reduced to linear algebra. At the moduli customary in CKKS, the ring element a is invertible with high probability, so s = a⁻¹·c follows: a single ciphertext together with its decryption result suffices. Only for moduli that are powers of two are several needed.

The side condition: the attacker must be able to reconstruct the encoding of the plaintext exactly, which requires a bound on the error norm; for large plaintexts a lattice attack applies instead, which is polynomial but not implemented in the paper.

What the Paper Claims – and What It Does Not

This is where summaries regularly distort. The paper does not claim that CKKS is not IND-CPA secure. It says that the traditional formulation of IND-CPA "does not adequately capture security against passive adversaries when applied to approximate encryption schemes", and that a different, stronger definition is required. The authors propose that definition; in the revision it is called IND-CPA^D, where the D explicitly indicates that decryption results are revealed to the adversary.

And a reading of the threat model belongs with this, or the finding sounds more dramatic than it is for many architectures: the attack presupposes that the attacker sees both a ciphertext known to them and its decryption result. In the simple outsourcing model — the data owner encrypts, the server computes, only the data owner decrypts and does not pass on the result — that is not the case. It becomes acute where decryption results are shared: in threshold schemes, multi-party evaluations, and anywhere results are published.

The Fix – and Why the Dividing Line Is Not at "Exact"

The remedy came a year later, from Baiyu Li, Daniele Micciancio, Mark Schultz and Jessica Sorrell: Securing Approximate Homomorphic Encryption Using Differential Privacy (CRYPTO 2022). The result: it suffices to add "Gaussian noise to the output of CKKS decryption" to achieve IND-CPA^D security, with "nearly matching upper and lower bounds" on the amount of noise required. The paper also names a pitfall: mechanisms whose noise parameters are tailored to the actual error of the individual ciphertext rather than to the worst-case error remain "vulnerable to IND-CPA^D attacks".

And here comes the twist that corrects the obvious lesson of the incident. One is tempted to conclude: approximate is dangerous, exact is safe. That is not true. With exact encryption, a correct decryption result reveals nothing new to the attacker directly — but only as long as decryption really is always correct. In 2024, Checri, Sirdey, Boudguiga and Bultel showed in On the practical CPA^D security of "exact" and threshold FHE schemes and libraries (CRYPTO 2024) that the "exact" schemes, too, decrypt correctly only with high, not with full probability: they construct "a CPA^D key recovery attack on the linearly homomorphic Regev cryptosystem" which, by their account, "easily generalizes to other xHE schemes such as BFV, BGV and TFHE", and they record that "existing threshold variants of BFV, BGV and CKKS are particularily exposed to CPA^D attackers". The attack is implemented, runs against common libraries, and according to the paper requires less than an hour on an average laptop.

The dividing line therefore does not run between exact and approximate, but between perfect and non-perfect correctness. The CKKS incident was not a special case of approximation but the first visible case of a more general gap.

The lesson is broader than CKKS and broader than FHE: a security definition is a model of adversary capabilities. When a scheme emits information the model did not anticipate — a residual noise, a rare decryption failure — then what is wrong is neither the code nor the mathematics, but the assumption that the definition is independent of the computational model.

Part 7: What Fully Homomorphic Encryption Does Not Deliver

The Homomorphic Encryption Standard, published in 2018 by a group from industry, research and government (HomomorphicEncryption.org, 21 November 2018; authors including Albrecht, Chase, Goldwasser, Halevi, Laine, Lauter, Micciancio, Moody, Sahai, Vaikuntanathan), is remarkably candid on this point. It sets "Semantic Security or IND-CPA Security" as the security goal — and then names what that does not cover.

No protection against an active server. The document walks through exactly this case: the client has F(M) computed, but the cloud returns a ciphertext of G(M) for some other function G. Verbatim: "This is an example of an active attack which is not ruled out by semantic security." And further: "Such attacks are not addressed by the semantic security guarantee, countering them requires additional measures beyond the use of homomorphic encryption." FHE guarantees confidentiality of the inputs, not correctness of the result. Anyone who needs the latter needs an additional mechanism.

No CCA2 security – as long as anyone may compute. The malleability of the ciphertext is not a defect in FHE but the desired property: whoever can modify the ciphertext in a targeted way can compute on it. In On CCA-Secure Fully Homomorphic Encryption (ePrint 2010/560), Loftus, May, Smart and Vercauteren state the common reading: "any encryption scheme which supports any form of homomorphic operation cannot be secure against adaptive chosen ciphertext attacks". What matters is how that sentence appears there: as a preliminary remark, introduced with "It is well known that", without proof and without a citation. The paper's theorems concern something else — they show that "the basic Gentry scheme is not IND-CCA1", and that a minor modification of a variant of the Smart-Vercauteren scheme achieves IND-CCA1, "indeed PA-1".

There is no formal impossibility result, and one would also be too strong. The argument — modify the ciphertext, query the decryption oracle — presupposes that the homomorphic operation is publicly and unboundedly executable. Remove either premise and CCA-style security becomes attainable: Prabhakaran and Rosulek (ICALP 2008) define CCA security relative to a permitted set of transformations; Boneh, Segev and Waters restrict malleability with targeted malleability (ITCS 2012) to "a specific set of 'allowable' functions"; and Emura and co-authors (PKC 2013) bind the homomorphic operation to a dedicated secret evaluation key — "By introducing a secret key for homomorphic operations, we can control who is allowed to perform the homomorphic operation." For the cloud scenario, in which precisely anyone is supposed to be able to compute, the statement remains practically correct — but it is a consequence of the architecture, not a theorem of cryptography.

No secrecy of the computation, at least not by default. That the ciphertext conceals which operations led to it, the standard calls "a desirable additional security property beyond semantic security" — a desirable additional property, then, not an existing one. For BGV it says the evaluation algorithms can be augmented to provide evaluation privacy "with respect to semi-honest adversaries"; for BFV a corresponding augmentation is mentioned, there without this explicit adversary qualification. It is an option, not default behaviour.

The Neighbouring Technologies, Fairly Compared

Confidential computing solves the same underlying problem (data in use) by shifting trust to the chip manufacturer and an attestation chain. FHE solves it via a hardness assumption and needs no trusted hardware vendor for that — but pays with four to five orders of magnitude in computation time, with the circuit model, and with the fact that confidential computing attests the integrity of the computation as well, whereas FHE, per the standard cited above, precisely does not guarantee it.

Zero-knowledge proofs address the other half, but differently than the shorthand suggests. They deliver two things: soundness, meaning a false statement will not convince the verifier, and zero-knowledge, meaning the verifier learns nothing about the private witness that it did not already know — the ZKProof Community Reference formulates it as the property of not leaking anything about the witness "beyond what the attacker may already know about the witness from other sources". Zero-knowledge is, therefore, a confidentiality property of the inputs. What ZK does not deliver is outsourcing: in a ZK proof the data owner computes, because they know the witness. FHE conversely lets a third party compute on data it never sees, but does not guarantee that it computed the right thing. The two techniques are complementary, not competing.

Differential privacy protects something different — not the data on its way into the computation, but the individual in the published result. That the CKKS fix works with a DP mechanism is less a coincidence than the clean analysis of an old technique: noise flooding has long been customary in lattice cryptography; the differential-privacy calculation provides, for the first time, nearly tight upper and lower bounds on the amount required.

Part 8: Where It Actually Runs Today

The most common objection to FHE is that it is research. Since 2024 that is no longer right — although in a very specific form.

On 30 July 2024, Apple released the library swift-homomorphic-encryption as open source (post by Fabian Boemer, Karl Tarbe and Rehan Rishi). It implements the Brakerski-Fan-Vercauteren (BFV) scheme. The product application named is Live Caller ID Lookup in iOS 18: the service "uses homomorphic encryption to send an encrypted query to a server that can provide information about a phone number without the server knowing the specific phone number in the request". Technically it is a private information retrieval scheme: a key-value lookup in which the server does not learn the keyword queried. The post states explicitly: "the server itself never decrypts the original data or even has access to the decryption key."

Two qualifications belong with this. First, the post does not foreground ciphertext sizes or latencies; the parameter set named in the example code is explicitly marked ("These encryption parameters are insecure, suitable for testing only."), and for the product application it says only that it requires "BFV parameters with post-quantum 128-bit security", without concrete values. Which PIR protocol is used is not apparent from the published documents.

Second, and this is the more important framing: Live Caller ID Lookup is a lookup, not an arbitrary computation. PIR is among the FHE applications with the most favourable benefit-to-cost ratio, because the circuit shape is fixed and its depth known in advance and independent of the query — no bootstrapping is needed, the scheme stays leveled. Shallow, however, the circuit is not: the common single-server constructions rely precisely on homomorphic multiplication. MulPIR uses "multiplicative homomorphism to implement the recursion steps in PIR", explicitly "at the cost of an increased computational cost for the server"; Spiral uses a sequence of external products between Regev and GSW ciphertexts with noise management and modulus switching, arguing over noise growth after k sequential multiplications. That FHE runs in production here is a genuine finding — but it does not transfer straightforwardly to arbitrary outsourcing of business logic.

Fact Check

For this article, 89 checkable claims were extracted and verified against primary sources: 69 claims in classes (a) hard facts, (b) verbatim quotations and (c) source attributions — of which 47 had a factual, 17 a quotation and 14 an attribution component, with individual claims falling into more than one class — plus 20 synthesis claims in class (d). The check was performed by two separate reviewer instances, which received the draft and the source list and were tasked with finding errors; for the synthesis claims, counter-evidence and limiting follow-up work were actively searched for in addition. Result: 60 CONFIRMED, 9 FALSE, 17 TO BE WEAKENED, 3 NOT VERIFIABLE. 29 claims were corrected, weakened or struck.

The most important corrections:

1. The draft's explanatory mechanism for the CKKS attack was invented. The draft claimed that the residual noise depends on the secret key and therefore reveals it after enough observations. The actual mechanism is the opposite: anyone who knows the approximate decryption result m + e and subtracts it from the ciphertext component cancels the error and obtains an error-free linear equation — a single ciphertext suffices at the customary moduli. Part 6 was rewritten accordingly.
2. The core lesson of Part 6 ("exact is safe, approximate is not") was wrong. At CRYPTO 2024, Checri, Sirdey, Boudguiga and Bultel demonstrate the same attack type against BFV, BGV and TFHE, because the "exact" schemes, too, do not decrypt with perfect correctness. The dividing line was moved from "exact versus approximate" to "perfect versus non-perfect correctness" — which also changes the central takeaway.
3. Gentry's bootstrapping theorem was rendered without its circularity assumption. Bootstrappability yields only leveled FHE at first; unbounded depth with a single key pair presupposes that the encryption of the secret key under its own public key is secure — an assumption not proven from any standard problem. The section was amended.

Further substantive corrections: the draft had swapped the logarithmic dependencies in the squashing argument — the evaluable depth depends doubly logarithmically on the noise radii, while the lattice dimension sits in the decryption circuit; the claim that bootstrapping is "indispensable" for unbounded depth was reduced to "the only means known from lattice assumptions", because a construction from indistinguishability obfuscation exists; the claim that an encrypted database access necessarily becomes a full scan was qualified by the counter-finding of doubly efficient PIR from Ring LWE, as was loop unrolling by the Turing-machine construction of Goldwasser et al.; the reticence about cost figures was excessive — the measured characterization of 10,000x to 100,000x from the MICRO 2021 paper on F1 was added, and "many orders of magnitude" was correctly attributed on the DARPA page as the required reduction rather than the current state; the portrayal of zero-knowledge proofs as techniques that do not concern "confidentiality of the inputs" was false and was replaced, the real difference lying in outsourcability; the CCA2 claim was reduced from "ruled out in principle" to "ruled out as long as the homomorphic operation is publicly and unboundedly executable", with the three counter-examples Prabhakaran/Rosulek, Boneh/Segev/Waters and Emura et al.; "shallow" was struck from the PIR argument, because MulPIR and Spiral rely precisely on homomorphic multiplication; the claim that the ISO series follows the division into scheme families "exactly" was refined to three mechanism parts against four schemes, and the mapping marked as a reading, since the titles of the parts name no schemes; Part 5 of the series is not an "admission" but the standardization of an idea already motivated that way in the 2018 CHIMERA paper; "CKKS is the scheme for machine learning" was restricted to the arithmetic part, because the article itself assigns activation functions to table evaluation; the claim about RAD78 and comparisons against constants was narrowed to reading off the comparison result, since it otherwise contradicted the TFHE section; the OpenFHE figure "under 100 ms" was attributed to the FHEW/TFHE-style schemes rather than to non-linear operations in general; evaluation privacy with the semi-honest qualification applies, per the source, to BGV, not to BFV; the attribution of the Gentry quotation was corrected from the introductory chapter to the abstract; the 1978 lender was a small loan company at a time-sharing service; and "a quarter of a century" contradicted the triply documented figure of 31 years. Three unsubstantiable claims about discourse ("overstretched in sales conversations", "regularly skipped", "the most instructive incident") were struck or marked as the author's own assessment, as was the negative existence claim about missing latency figures in the Apple post.

Note: automated AI verification against primary sources; no human expert review. Open in this run is whether the ISO standard texts themselves name BGV, BFV, CKKS and TFHE explicitly — the retrieved catalogue pages do not, and the standard texts were not accessible. The stage codes and dates in the table come from the ISO committee pages at the time of retrieval and may have advanced since.

The Central Takeaway

Fully homomorphic encryption looks at first like the end of a dilemma: outsource data without disclosing it. After working through the primary literature, three insights remain, and all three are uncomfortable.

The first: FHE guarantees confidentiality of the inputs, not correctness of the result. This is not in the fine print but in the field's own standard, with a worked example: the server can simply compute G(M) instead of F(M), and semantic security explicitly does not rule that out. Any architecture in which a decision follows from the result of an outsourced computation therefore needs a second mechanism for integrity. Anyone who deploys FHE without having discussed integrity has solved only half the problem — and possibly the easier half.

The second: the cost problem is only half cryptography. Four to five orders of magnitude relative to plaintext computation is one half. The other is that the computation must be cast into a circuit whose shape may not depend on the data. Every if becomes both branches, every loop its worst case, every indexed access a full scan. There are theoretical ways out, but none in practical use. Which means: the feasibility question is not a benchmark but a question about the shape of your own algorithm.

The third, and the most general: the security definition is part of the system, not part of the theory. CKKS was correctly implemented, the mathematics was sound, and the scheme satisfied the definition it was built on. Complete key recovery from a single ciphertext became possible because the scheme emitted information — plaintext plus residual noise — that the adversary model had not anticipated. And in 2024 it turned out that the same gap exists in the "exact" schemes, because their correctness holds only with high probability. The dividing line does not run between exact and approximate, but between perfect and non-perfect correctness.

The practical prompt that follows is a single question, answerable within an hour for any planned FHE deployment — and it decides whether you are in the IND-CPA or the IND-CPA^D threat model: do decryption results ever leave the trust boundary of the key holder? If only the data owner decrypts and keeps the result, the classical definition holds up. As soon as results are shared, published, or jointly decrypted in a threshold scheme, IND-CPA is the wrong yardstick, and you need noise flooding per the differential-privacy calculation — calibrated to the worst-case error, not to the actual one.

The concrete first step, doable in a week when an FHE project is under discussion: take the computation that is to be outsourced and write it out as a circuit — with the multiplicative depth stated and every if explicitly resolved into both branches. If that does not fit on one page because the depth depends on the data, the answer to the feasibility question is already given, independently of any benchmark and any hardware generation.

Reflection Question

Confidential computing shifts trust onto a chip manufacturer and an attestation chain — onto something you can name, inspect and address contractually, but which is compromisable. Fully homomorphic encryption shifts it onto a mathematical hardness assumption — and, for unbounded depth, additionally onto a circularity assumption for which there is no hardness proof and which you cannot enforce against anyone, because it has no addressee.

Which of these two forms of trust would you rather take on for a concrete project — and, more importantly: on which property would you pin the difference? On the fact that one would be noticeable if it failed and the other would not? On the fact that one has someone liable? Or on the fact that mathematical assumptions age quietly, while hardware breaks loudly?

And does your answer change if you are not the one outsourcing, but the person whose data is being computed on?

Cross-References in the Vault

• Computing in a Sealed Room: Confidential Computing and the Limits of Not Trusting – the direct alternative to the same problem, data in use, with the inverse trust model: silicon and attestation instead of a hardness assumption. The decisive difference, where both articles converge: confidential computing attests the integrity of the computation as well, FHE does not guarantee it.
• Proving Without Revealing: Zero-Knowledge Proofs from Ali Baba's Cave to zk-SNARKs – the complementary half: proving correctness without revealing the witness. Exactly what FHE lacks — which is why the two are combined in practice rather than weighed against each other.
• The Noise That Protects Privacy: Differential Privacy and the Art of Revealing Nothing About the Individual – the surprising point of contact: the fix for the CKKS security gap is a differential-privacy mechanism applied to the decryption result, with nearly tight bounds on the amount of noise required.
• Harvest Now, Decrypt Later: Post-Quantum Cryptography and the Race Against the Quantum Computer – the same lattice world from the other side. Learning With Errors and Ring-LWE carry both the post-quantum standards and every FHE scheme in use today; anyone assessing one is assessing the assumption behind both.
• The Man Who Toppled Three Agreements: Max Schrems, Transatlantic Data Transfers, and the Puzzle of Adequacy – the legal motivation behind the technical effort: FHE is one of the few candidates for a supplementary measure in which the recipient technically cannot read the data. What the technique does not deliver — integrity, hiding the computation — matters as much to that assessment as what it does.

Sources and Further Reading

1. Ronald L. Rivest, Len Adleman, Michael L. Dertouzos: On Data Banks and Privacy Homomorphisms, in: Foundations of Secure Computation (eds. DeMillo, Dobkin, Jones, Lipton), Academic Press 1978, pp. 165–179. Checked: the definition of privacy homomorphisms, the example count, the authors' own assessment of chosen-plaintext vulnerability, and the limit on comparisons against constants. PDF at MIT CSAIL · BibTeX
2. Oded Regev: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography; results originally published in 2005, version checked dated 2 May 2009. Checked: the LWE definition, Theorem 1.1 (Õ(n/α), αp > 2√n, GAPSVP/SIVP) and the statements on the quantum nature of the reduction. PDF
3. Craig Gentry: A Fully Homomorphic Encryption Scheme, dissertation, Stanford University, September 2009 — bootstrapping, squashing, the depth estimates and the second hardness assumption. PDF · Conference version: Fully Homomorphic Encryption Using Ideal Lattices, STOC 2009, DOI 10.1145/1536414.1536440 (abstract · publication record)
4. Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan: Fully Homomorphic Encryption without Bootstrapping (BGV), 2011 — leveled FHE, Õ(λ·L³) per gate, Õ(λ²) with bootstrapping, Õ(λ) with batching for wide circuits. ePrint 2011/277
5. Ran Canetti, Huijia Lin, Stefano Tessaro, Vinod Vaikuntanathan: construction of non-leveled FHE without circular security, from sub-exponentially hard indistinguishability obfuscation — the citation for the role of the circularity assumption in all bootstrapping-based constructions. ePrint 2014/882
6. Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, Malika Izabachène: TFHE: Fast Fully Homomorphic Encryption over the Torus, Journal of Cryptology 2019 (full version of Asiacrypt 2016 and 2017) — 690 ms → 13 ms single core, 1 GB → 16 MB bootstrapping key, 137 ms circuit bootstrapping, look-up tables. ePrint 2018/421
7. Jung Hee Cheon, Andrey Kim, Miran Kim, Yongsoo Song: Homomorphic Encryption for Arithmetic of Approximate Numbers (CKKS), ASIACRYPT 2017 — rescaling, the precision bound of at most one additional bit, linear growth of the ciphertext modulus with depth. ePrint 2016/421
8. Baiyu Li, Daniele Micciancio: On the Security of Homomorphic Encryption on Approximate Numbers, EUROCRYPT 2021 — passive attacks on CKKS with complete key recovery, tested against HEAAN, SEAL, HElib and PALISADE; introduction of the IND-CPA^D notion. ePrint 2020/1533
9. Baiyu Li, Daniele Micciancio, Mark Schultz, Jessica Sorrell: Securing Approximate Homomorphic Encryption Using Differential Privacy, CRYPTO 2022 — Gaussian noise on the decryption output suffices for IND-CPA^D; mechanisms calibrated to the actual rather than the worst-case error remain attackable. ePrint 2022/816
10. Marina Checri, Renaud Sirdey, Aymen Boudguiga, Jean-Paul Bultel: On the practical CPA^D security of "exact" and threshold FHE schemes and libraries, CRYPTO 2024 — generalization of the attack type to BFV, BGV and TFHE via non-perfect decryption correctness; particular exposure of the threshold variants. ePrint 2024/116
11. Albrecht, Chase, Chen, Ding, Goldwasser, Gorbunov, Halevi, Hoffstein, Laine, Lauter, Lokam, Micciancio, Moody, Morrison, Sahai, Vaikuntanathan: Homomorphic Encryption Standard, HomomorphicEncryption.org, 21 November 2018 (v1.1) — IND-CPA as the security goal, active attacks explicitly not covered, evaluation privacy as a desirable additional property. standard page
12. J. Loftus, A. May, N. P. Smart, F. Vercauteren: On CCA-Secure Fully Homomorphic Encryption — the common reading on CCA2 impossibility (stated there as a preliminary remark without proof), the CCA1 attack on the basic Gentry scheme, and the PA-1 construction. ePrint 2010/560
13. Dan Boneh, Gil Segev, Brent Waters: Targeted Malleability: Homomorphic Encryption for Restricted Computations, ITCS 2012 — restricting malleability to a permitted set of functions as a route to CCA-style security. ePrint 2011/311; additionally Prabhakaran/Rosulek, Homomorphic Encryption with CCA Security, ICALP 2008 (ePrint 2008/079) and Emura et al., PKC 2013, on the secret evaluation key (ePrint 2013/390)
14. Nikola Samardzic, Axel Feldmann, Aleksandar Krastev, Srinivas Devadas, Ronald Dreslinski, Christopher Peikert, Daniel Sanchez: F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption, MICRO 2021 — the measured characterization "10,000× to 100,000× slower than unencrypted computation" for optimized software FHE, plus the note on data movement as the bottleneck. arXiv PDF
15. DARPA: Data Protection in Virtual Environments (DPRIVE) — program page, marked complete; goal "within a factor of ten of unencrypted computations", reduction target "by many orders of magnitude". darpa.mil
16. Al Badawi, Alexandru, Bates, Bergamaschi, Cousins, Erabelli, Genise, Halevi, Hunt, Kim, Lee, Liu, Micciancio, Pascoe, Polyakov, Quah, Saraswathy, Rohloff, Saylor, Suponitsky, Triplett, Vaikuntanathan, Zucca: OpenFHE: Open-Source Fully Homomorphic Encryption Library, WAHC 2022 — scheme coverage, "fast functional bootstrapping (under 100 ms)" for the FHEW/TFHE-style schemes, relative mode costs of 1.2x to 1.5x. ePrint 2022/915
17. Shafi Goldwasser, Yael Tauman Kalai, Raluca Ada Popa, Vinod Vaikuntanathan: How to Run Turing Machines on Encrypted Data, CRYPTO 2013 — the drawback of the circuit model and a construction whose costs depend on the actual running time. ePrint 2013/229; and Wei-Kai Lin, Ethan Mook, Daniel Wichs: Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE, CRYPTO 2023 — sub-linear server running time after preprocessing. ePrint 2022/1703
18. ISO/IEC JTC 1/SC 27: standards series ISO/IEC 28033 Information security — Fully homomorphic encryption, Parts 1 to 5 — titles, stage codes and stage dates at the time of retrieval. Part 1 · Part 2 · Part 3 · Part 4 · Part 5
19. Fabian Boemer, Karl Tarbe, Rehan Rishi: Announcing Swift Homomorphic Encryption, swift.org, 30 July 2024 — the BFV implementation, Live Caller ID Lookup in iOS 18 as a PIR application, statements on the server's key access. swift.org
20. Christina Boura, Nicolas Gama, Mariya Georgieva, Dimitar Jetchev: CHIMERA: Combining Ring-LWE-based Fully Homomorphic Encryption Schemes, 2018 — scheme switching as a response to standardization initiatives and common APIs. ePrint 2018/758; additionally, on PIR constructions using homomorphic multiplication: Ali et al., Communication-Computation Trade-offs in PIR (MulPIR), USENIX Security 2021 (ePrint 2019/1483)

Note: this article is a technical account of the state of research and standardization, not security advice for any specific project. The statements on the standardization status of the ISO/IEC 28033 series are based on the committee pages at the time of retrieval and should be re-checked before any decision.

← All articles