Computing on Ciphertext: The FHE Promise, Noise Growth, and Why Bootstrapping Is the Central Idea

Abstract

This opening article establishes what fully homomorphic encryption (FHE) promises and why it is hard. It defines the homomorphic property — that operations on ciphertexts map to operations on the underlying plaintexts, so a party can compute on data it cannot read — and grounds it in the lattice encryption whose additive structure makes addition on ciphertext natural. It then introduces the central obstacle: every homomorphic operation grows a noise term in the ciphertext, slowly under addition and sharply under multiplication, and once the noise crosses a threshold the ciphertext no longer decrypts. This bounds a naive scheme to a fixed circuit depth, giving leveled FHE. Finally it presents Gentry's breakthrough, bootstrapping — homomorphically evaluating the scheme's own decryption circuit to refresh a noisy ciphertext into a fresh low-noise one — which lifts the depth bound and makes fully homomorphic (unbounded) computation possible in principle. It closes with the motivating application: private inference, where a hosted model computes on an encrypted prompt it never sees in the clear. The theme: FHE is computing on ciphertext, its enemy is noise growth, and bootstrapping is the idea that tames it.

Encryption normally forces a choice: keep data confidential, or compute on it, but not both — to process encrypted data you must first decrypt it, exposing it. Fully homomorphic encryption breaks that trade-off. It lets a party perform arbitrary computation directly on ciphertext, producing an encrypted result that, when decrypted by the key holder, equals the result of the same computation on the plaintext — without the computing party ever seeing the data. This article builds the idea from its foundation, confronts the obstacle that made it seem impossible for thirty years, the relentless growth of noise, and presents the single insight, bootstrapping, that resolved it and opened the door to confidential AI.

The promise of computing on ciphertext

The defining property of homomorphic encryption is that operations on ciphertexts correspond to operations on the plaintexts they hide. Add two ciphertexts and decrypt the result, and you get the sum of the two underlying messages; multiply two ciphertexts and decrypt, and you get their product. A scheme that supports both addition and multiplication on encrypted data supports, in principle, any computation, because arithmetic circuits over addition and multiplication can express arbitrary functions.

The consequence is a new capability: a party can compute a function on data it is not permitted to read. A client encrypts its input under its own key and sends only the ciphertext to a server; the server evaluates the function homomorphically, producing an encrypted output; the client decrypts to recover the result. The server never possesses the plaintext input or output, yet performs the work. This is the promise that motivates the entire field — outsourced computation with input privacy guaranteed by cryptography rather than by trust.

The flow makes the roles explicit. Encryption happens on the trusted client with the secret key; homomorphic evaluation happens on the untrusted server with only the public key and the ciphertext; decryption returns to the client. Confidentiality is preserved end to end because the data is in ciphertext for its entire time outside the client. The rest of this article is about what makes this possible and what makes it expensive.

The client encrypts and decrypts; the untrusted server computes on ciphertext and never sees plaintext.

Why it is possible: homomorphic structure and noise

The homomorphic property comes from the algebraic structure of lattice encryption. In a learning-with-errors ciphertext, the message is embedded together with the secret and a small random error term, so that decryption recovers the message only when the error is small. Crucially, the encryption is linear enough that adding two ciphertexts produces a ciphertext of the sum, and a suitable product operation produces a ciphertext of the product — the arithmetic on ciphertexts mirrors the arithmetic on plaintexts.

But the same error term that provides security is what makes the scheme fragile under computation. Decryption is correct only while the error stays below a threshold relative to the modulus. A fresh ciphertext has small error; every homomorphic operation combines the errors of its inputs and therefore enlarges the error of the output. The scheme computes correctly precisely as long as this accumulated error remains under the decryption threshold.

The two operations grow error very differently. Addition adds the errors, so the error grows roughly linearly with the number of additions — cheap. Multiplication combines the errors multiplicatively, so error grows far faster with multiplicative depth — expensive. This asymmetry is the reason multiplicative depth, not raw operation count, is the quantity that governs the cost and feasibility of a homomorphic computation.

\[\mathsf{Dec}\big(\mathsf{Enc}(m_1) \oplus \mathsf{Enc}(m_2)\big) = m_1 + m_2, \qquad \mathsf{Dec}\big(\mathsf{Enc}(m_1) \otimes \mathsf{Enc}(m_2)\big) = m_1 \cdot m_2\]

\[b = \langle a, s \rangle + e + \lfloor q/2 \rfloor \cdot m \pmod q, \qquad \text{decryption correct} \iff |e| < q/4\]

\[|e_{\mathsf{add}}| \approx |e_1| + |e_2|, \qquad |e_{\mathsf{mult}}| \gg |e_1| + |e_2|\]

The noise-growth problem and leveled FHE

Because error accumulates and decryption fails once it crosses the threshold, a naive homomorphic scheme can evaluate only circuits up to a bounded depth before its ciphertexts become undecryptable garbage. This is not a minor inconvenience; it is the wall that confined homomorphic encryption to limited, special-purpose schemes for decades. A scheme that supports a fixed, predetermined amount of computation — enough multiplicative depth for a known circuit, but no more — is called leveled fully homomorphic encryption.

Leveled schemes are genuinely useful. If the target computation has known, modest multiplicative depth, one can choose parameters large enough that the noise budget covers the whole circuit, and no further machinery is needed. Techniques such as modulus switching and relinearization manage the noise and ciphertext size along the way, stretching how much a leveled scheme can do for a given parameter choice. Much practical FHE deployment today is leveled, tuned to a specific circuit.

The limitation is that the depth must be bounded in advance and paid for in parameter size: deeper circuits demand larger parameters, which slow every operation and enlarge every ciphertext. A leveled scheme cannot evaluate an arbitrary or unbounded computation. Reaching truly fully homomorphic encryption — unbounded depth with fixed parameters — requires a way to reduce noise mid-computation rather than merely budgeting for it. That is what the next idea provides.

A fresh ciphertext has a small noise budget; additions spend it slowly and multiplications quickly, until the threshold is crossed.

Bootstrapping: the central idea

Gentry's 2009 breakthrough was to remove noise mid-computation by a procedure called bootstrapping. The insight is startling in its self-reference: take a noisy ciphertext and homomorphically evaluate the scheme's own decryption function on it, using an encryption of the secret key. The homomorphic decryption produces a new ciphertext of the same message, but its noise is the small, fresh noise introduced by the bootstrapping operation rather than the large accumulated noise of the input. The ciphertext has been refreshed without ever being decrypted in the clear.

This closes the loop that makes unbounded computation possible. Compute until the noise approaches the threshold, bootstrap to reset it to a low level, then continue computing — repeating as often as needed. Because each bootstrap restores the noise budget, there is no fixed depth limit, and the scheme becomes fully (not merely leveled) homomorphic. Bootstrapping is therefore the conceptual heart of FHE: it is the operation that converts a depth-bounded scheme into an unbounded one.

The catch, previewed here and detailed later in the series, is cost. Homomorphically evaluating a decryption circuit is itself an expensive computation, and bootstrapping is typically the dominant term in the runtime of a fully homomorphic evaluation. The entire practical art of FHE is a balance between doing more work between bootstraps (larger parameters, more noise budget) and bootstrapping more often (smaller parameters, more frequent refresh). But the existence of bootstrapping is what turned FHE from a thirty-year open problem into a real technology.

Compute until noise nears the threshold, bootstrap to refresh it, and continue — removing the depth bound.

The motivating application: private inference

The application that drives modern interest in FHE is private machine-learning inference, and it maps directly onto the flow established above. A client encrypts its input — a prompt, an image, a medical record — under its own key and sends only the ciphertext to a hosted model. The model provider evaluates the network homomorphically and returns an encrypted output, which only the client can decrypt. The provider runs the model but never sees the plaintext input or the plaintext result, so confidentiality is guaranteed by cryptography rather than by a promise or a policy.

This is a qualitatively stronger guarantee than the usual assurances around a hosted service. There is no plaintext for an insider to read, for a compromise to leak, or for a subpoena to compel, because the data never exists in the clear on the provider's side. For regulated data — health, finance, confidential enterprise documents — that property is the difference between being able to use a hosted model and not. It is why FHE is treated as a foundational primitive for confidential AI rather than a cryptographic curiosity.

The tension, which the rest of the series unpacks, is between this ideal and its cost. Neural networks have substantial multiplicative depth and rely on non-linear functions that FHE does not evaluate natively, so private inference stresses exactly the noise-growth and bootstrapping machinery introduced here. Understanding what is feasible — which models, which layers, at what latency — requires understanding the scheme families, the true cost of bootstrapping, and how non-linearities are approximated. Those are the subjects of the articles that follow, but the frame is set: FHE computes on ciphertext, noise is the enemy, bootstrapping is the answer, and private AI is the prize.

📌

The one-sentence summary. Fully homomorphic encryption computes on encrypted data; every operation grows a noise term that eventually breaks decryption; bootstrapping homomorphically refreshes that noise, removing the depth limit and enabling private inference on a model that never sees the plaintext.

Key takeaways

Homomorphic encryption maps operations on ciphertext to operations on plaintext, so a party can compute a function on data it cannot read.
The property comes from lattice encryption whose small error term enables ciphertext arithmetic but must stay below a threshold for decryption to succeed.
Every operation grows the noise — slowly under addition, sharply under multiplication — so multiplicative depth governs feasibility; a fixed noise budget gives leveled FHE.
Bootstrapping homomorphically evaluates the scheme's own decryption to refresh a noisy ciphertext into a fresh one, removing the depth bound and making full (unbounded) FHE possible.
Bootstrapping is typically the dominant cost, so practical FHE balances computing more between bootstraps against bootstrapping more often.
Private inference is the motivating application: a hosted model computes on an encrypted prompt and returns an encrypted result, never seeing plaintext.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

✅Reasoning about an FHE workloadchecklist

Questions that determine feasibility and cost.

What is the multiplicative depth of the target computation?
Does a fixed depth suffice (leveled) or is unbounded depth needed (bootstrapping)?
How much noise budget do the chosen parameters provide?
Does the computation need exact integers or approximate reals?
Where do non-linear functions appear, and how will they be approximated?

🚀The FHE mental modelquickstart

The three facts to hold onto.

Ciphertext operations mirror plaintext operations (the homomorphic property).
Every operation grows noise; multiplication grows it fast.
Bootstrapping refreshes noise, removing the depth limit at a cost.

🔒Confidential-inference stancepolicy

A stub policy for FHE-based private inference.

confidential_inference:
  data_in_transit: ciphertext_only
  provider_sees_plaintext: false
  keys:
    held_by: client
    provider_access: none
  scheme:
    type: fhe
    mode: [leveled, bootstrapped]
  note: cost_scales_with_multiplicative_depth

Illustrative documentation template, not a product config.

Glossary

Homomorphic encryption: Encryption whose ciphertext operations correspond to plaintext operations, allowing computation on encrypted data.
Fully homomorphic encryption (FHE): A homomorphic scheme supporting both addition and multiplication to unbounded depth, hence arbitrary computation.
Noise / error: A small random term in a lattice ciphertext that provides security but grows with each operation and breaks decryption once it exceeds a threshold.
Leveled FHE: A scheme that supports a fixed, predetermined multiplicative depth without bootstrapping.
Bootstrapping: Homomorphically evaluating the scheme's own decryption circuit to refresh a noisy ciphertext into a low-noise one, removing the depth limit.
Multiplicative depth: The number of multiplications in series in a circuit; the quantity that most drives noise growth and FHE cost.