Bootstrapping and Its Cost: Refreshing Noise and the Parameter, Security, Performance Triangle

Abstract

This article examines the price of the operation that makes fully homomorphic encryption possible. Bootstrapping — homomorphically evaluating the scheme's decryption circuit to refresh a noisy ciphertext — is typically the single most expensive operation in a homomorphic computation, so total runtime is dominated by how many bootstraps a circuit needs times the cost of each. It explains why bootstrapping is heavy, then develops the central design tension: a larger ciphertext modulus buys more noise budget and thus more computation between bootstraps, but a larger modulus lowers the lattice security at a fixed dimension, forcing the dimension up to compensate, which slows every operation. Security, performance, and computational capability form a triangle in which improving one pressures the others. It surveys the levers that reduce cost — amortizing one bootstrap over many batched slots, better bootstrapping algorithms for CKKS and the fast TFHE style, hardware acceleration, and shallow-circuit co-design — and closes with the AI consequence: bootstrapping dominates private-inference latency, and deeper networks demand more refreshes, which is why making confidential inference practical is largely the engineering of bootstrapping. The theme: bootstrapping is both the enabling idea and the dominant cost of FHE, governed by a security/performance/capability triangle.

Bootstrapping is what turns a depth-limited homomorphic scheme into a fully homomorphic one, but that power is not free — bootstrapping is almost always the dominant cost in a homomorphic computation, and understanding its price is essential to understanding what FHE can and cannot do in practice. The cost is not a fixed number; it emerges from a three-way tension between security, performance, and how much computation a ciphertext can absorb before it must be refreshed. This article explains why bootstrapping is expensive, lays out that tension as a design triangle, surveys the levers that reduce the cost, and connects it to the latency of private machine-learning inference.

Why bootstrapping dominates the cost

Bootstrapping is expensive because of what it is: the homomorphic evaluation of the scheme's own decryption function. Decryption is not a trivial circuit, and evaluating it under encryption — on a ciphertext, using an encrypted copy of the secret key — requires a substantial sequence of homomorphic operations, often with its own significant multiplicative depth. A single bootstrap can cost orders of magnitude more than a single homomorphic addition or multiplication, which is why it dominates the runtime of any computation deep enough to require it.

The total cost of a homomorphic evaluation therefore separates into two very unequal terms: the ordinary arithmetic of the computation, and the bootstraps needed to keep the noise in check along the way. Because each bootstrap is so much heavier than each arithmetic operation, the number of bootstraps a circuit forces is usually the number that determines its feasibility. Reducing bootstraps — or making each one cheaper — is the central performance problem of FHE.

This is why leveled evaluation, which avoids bootstrapping entirely for circuits of bounded depth, is so attractive when it applies: if a computation fits within a single noise budget, it pays none of the bootstrapping tax. The trouble is that many valuable computations, deep neural networks among them, exceed any practical single budget, so they must bootstrap, and the cost of doing so becomes the thing to engineer around. The parameters that set the size of the noise budget are where that engineering begins.

\[T_{\text{total}} \approx (\#\,\text{bootstraps}) \times T_{\text{bootstrap}} + T_{\text{arith}}, \qquad T_{\text{bootstrap}} \gg T_{\text{arith}}\]

The parameter, security, performance triangle

The size of the noise budget is controlled mainly by the ciphertext modulus: a larger modulus leaves more room for noise to grow before it crosses the decryption threshold, so a ciphertext can absorb more computation between bootstraps. It is tempting to simply enlarge the modulus and bootstrap less often. But the modulus does not move freely, because it is bound to security.

The security of a lattice ciphertext depends on the ratio between the lattice dimension and the logarithm of the modulus: for a fixed dimension, increasing the modulus makes the underlying lattice problem easier and lowers the security level. To raise the modulus while holding security constant, one must also raise the dimension — and a larger dimension makes every homomorphic operation, and every bootstrap, slower and every ciphertext larger. The lever that buys computational headroom therefore pushes directly against performance once security is held fixed.

These three quantities — security, performance, and computational capability (the noise budget between bootstraps) — form a triangle in which you cannot freely improve all at once. More capability at fixed security costs performance; more performance at fixed security costs capability; holding both requires accepting a lower security margin, which is not an option below the target level. Every practical FHE parameter set is a chosen point in this triangle, and there is no point that is best on all three axes.

Parameter choices trade off among security, performance, and computational capability; improving one pressures the others.

\[\text{noise budget} \;\propto\; \log q, \qquad \text{security} \;\downarrow\; \text{ as } \log q \uparrow \text{ at fixed dimension } n\]

\[\text{hold security} \;\Rightarrow\; n \uparrow \text{ with } \log q \;\Rightarrow\; \text{runtime and ciphertext size} \uparrow\]

The levers that reduce the cost

The first and most important lever is amortization through batching. Because a single ciphertext packs many plaintext slots, one bootstrap can refresh all of them at once, so the per-value cost of bootstrapping falls as the batch grows. Structuring a computation so that a bootstrap serves thousands of packed values, rather than one, is often the difference between impractical and practical, and it is why throughput-oriented FHE thinks in terms of large batched tensors rather than scalar operations.

The second lever is better bootstrapping algorithms. Bootstrapping for CKKS has improved substantially since the scheme's introduction, and the FHEW/TFHE line was designed around a bootstrap so fast it runs after every gate, trading frequency for low individual cost and gaining the ability to evaluate arbitrary functions via programmable bootstrapping. Choosing the scheme and bootstrapping method suited to the computation's structure is itself a major cost lever. The third lever is hardware: bootstrapping is highly parallel and a strong target for GPU, FPGA, and dedicated ASIC acceleration, and specialized hardware is closing the gap toward practical latency.

The fourth lever is circuit co-design — shaping the computation to need fewer or shallower bootstraps. Reducing the multiplicative depth of a circuit, reordering operations to defer noise growth, and approximating expensive functions with low-depth polynomials all cut the number of refreshes required. In practice the levers combine: a well-engineered private computation batches aggressively, uses the right scheme and a modern bootstrap, runs on accelerated hardware, and is expressed as a shallow circuit. Together they have moved bootstrapping from prohibitively slow toward merely expensive.

Amortization, better algorithms, hardware, and circuit co-design stack to reduce the effective cost of bootstrapping.

The cost of private inference, and the AI stakes

For private machine-learning inference these abstractions become concrete latency. A neural network is a deep computation, and under FHE its depth translates into a number of bootstraps that grows with the number of layers — each block of linear algebra spends noise budget that a bootstrap must then restore before the next. The dominant term in the latency of homomorphic inference is almost always the bootstrapping, so the practical question of whether a given model can be served privately at an acceptable latency is largely a question about its depth and the cost of the bootstraps it forces.

This is why so much confidential-AI engineering effort targets exactly the levers above. Batching packs a whole layer's activations so one bootstrap refreshes them together; CKKS bootstrapping improvements and hardware accelerators cut the per-bootstrap time; and models are redesigned with lower-depth, FHE-friendly structure to reduce the bootstrap count. Progress on private inference is, to a large degree, progress on bootstrapping — the same operation, attacked from every direction at once.

The strategic reading is that the feasibility frontier of confidential AI moves precisely as bootstrapping gets cheaper. What is impractical at today's bootstrap cost becomes practical as amortization, algorithms, and hardware advance, so the set of models that can be served on encrypted prompts expands year over year. Understanding bootstrapping as the dominant, triangle-constrained cost is therefore not a narrow implementation detail; it is the lens through which to read what private inference can do now and what it will be able to do next. The enabling idea of FHE and its dominant cost are the same operation, and that is the fact to carry forward.

The number of bootstraps, and thus latency, grows with the depth of the network being evaluated under FHE.

Key takeaways

Bootstrapping homomorphically evaluates the scheme's decryption circuit and is typically the single most expensive operation, so runtime is dominated by bootstraps times per-bootstrap cost.
The noise budget grows with the ciphertext modulus, but a larger modulus lowers lattice security at fixed dimension, forcing the dimension up and slowing everything.
Security, performance, and computational capability form a triangle: improving one pressures the others, and every parameter set is a chosen point in it.
Cost levers: amortize one bootstrap over many batched slots, use better bootstrapping algorithms (CKKS, TFHE), accelerate in hardware, and co-design shallow circuits.
Leveled evaluation avoids bootstrapping for bounded-depth circuits and pays no refresh tax — attractive when the computation fits one noise budget.
Private inference latency is dominated by bootstrapping and grows with network depth, so the confidential-AI frontier advances as bootstrapping gets cheaper.

Practitioner Toolkit

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

✅Budgeting bootstrapping costchecklist

Questions that predict FHE latency.

How many bootstraps does the target circuit's depth force?
Can the noise budget (modulus) be enlarged without dropping below the security target?
Is the computation batched so one bootstrap refreshes many slots?
Are modern bootstrapping algorithms and hardware acceleration available?
Can the circuit be made shallower to cut the bootstrap count?

🚀The bootstrapping cost modelquickstart

Three facts to reason with.

Total time is roughly bootstraps times per-bootstrap cost, which dwarfs arithmetic.
Security ties the modulus to the dimension: more budget costs speed.
Batching, better algorithms, hardware, and shallow circuits are the levers.

🔒Parameter-selection stancepolicy

A stub recording the triangle decision.

fhe_parameters:
  security_target: 128_bit
  triangle:
    security: fixed_floor
    capability: noise_budget_from_modulus
    performance: dimension_and_size
  cost_levers: [batching, modern_bootstrap, hw_accel, shallow_circuit]
  rule: never_trade_below_security_floor

Illustrative documentation template, not a product config.

Glossary

Bootstrapping: Homomorphically evaluating the scheme's decryption to refresh a noisy ciphertext; the operation that removes the depth limit and dominates cost.
Noise budget: The amount of computation a ciphertext can absorb before its noise crosses the decryption threshold; grows with the modulus.
Ciphertext modulus (q): The modulus of the ciphertext ring; larger values give more noise budget but lower security at fixed dimension.
Lattice dimension (n): The dimension of the underlying lattice problem; raising it restores security but slows operations and enlarges ciphertexts.
Amortization / batching: Refreshing many packed plaintext slots with a single bootstrap, lowering the per-value cost.
Parameter triangle: The three-way tension among security, performance, and computational capability that no FHE parameter choice can optimize simultaneously.