Managing Noise in FHE:
Bootstrapping and Leveled Encryption

Noise is the central challenge in Fully Homomorphic Encryption. Every operation adds noise to ciphertexts, and when noise exceeds a threshold, decryption fails — a critical concern for anyone looking to compute on encrypted data in production. Understanding and managing noise is not merely an academic concern -- it is the single factor that determines whether an FHE system can run in production at scale or collapses under accumulated error. At H33, noise management is what allows us to sustain 1.595 million authentications per second with BFV encryption at ~42 microseconds per auth.

Why FHE Has Noise

FHE security relies on the Learning With Errors (LWE) problem -- small random errors injected into ciphertexts that make the underlying cryptographic problem computationally intractable. Without this noise, an attacker could solve a system of linear equations to recover the secret key. The noise is not a bug; it is the security mechanism itself. But it comes with a cost: every homomorphic operation compounds these errors.

• Fresh ciphertexts have small initial noise sampled from an error distribution
• Addition increases noise linearly -- the errors from both operands simply add together
• Multiplication increases noise dramatically -- the product of two noisy values amplifies errors quadratically
• Too much accumulated noise corrupts the plaintext, making decryption return garbage

Noise Budget

Think of noise budget as a finite resource that computation consumes. In BFV, the budget is typically measured in bits: the log-ratio between the maximum tolerable noise and the current noise magnitude. A fresh ciphertext might carry 40-60 bits of budget depending on parameters. Each operation draws down from that pool.

• Start with a fixed budget determined by the polynomial degree N and the ciphertext modulus Q
• Each operation consumes some budget -- additions cost fractions of a bit, multiplications cost 15-25 bits
• When budget reaches zero, decryption fails silently (returns incorrect plaintext)
• Larger initial budget demands larger parameters, which means bigger ciphertexts and slower operations

// Conceptual noise tracking
let noiseBudget = initialBudget;

c1 = encrypt(p1);  // Budget: 100%
c2 = encrypt(p2);  // Budget: 100%

c3 = add(c1, c2);  // Budget: ~95%
c4 = multiply(c3, c3);  // Budget: ~40%
c5 = multiply(c4, c4);  // Budget: ~5% - getting dangerous!

This is why H33 uses a single-depth multiplication circuit for biometric matching. The inner product of two 128-dimensional vectors requires only one level of plaintext-ciphertext multiplication followed by accumulation (addition). By keeping the depth at one, we preserve enough noise budget to guarantee correct decryption while using compact parameters: N=4096 with a single 56-bit modulus. The result is a ciphertext that fits in a few kilobytes, not megabytes.

The Parameter Tradeoff

Noise budget is not free. It is purchased with larger parameters, and larger parameters mean slower computation. The relationship between security, noise capacity, and performance forms a three-way tradeoff that every FHE deployment must navigate.

H33 navigates this tradeoff with what we call biometric_fast() parameters: N=4096 provides 128-bit security while keeping NTT transforms fast. A single 56-bit modulus Q avoids the overhead of CRT decomposition across multiple moduli. And t=65537 satisfies the CRT batching condition (t ≡ 1 mod 2N), which unlocks SIMD slot packing -- 4096 slots divided by 128 biometric dimensions gives 32 users per ciphertext.

Leveled FHE

Leveled FHE sets parameters based on known computation depth. Rather than supporting arbitrary circuits, you determine the maximum multiplication depth your application requires and choose parameters that provide exactly enough noise budget for that depth -- no more, no less.

• Determine maximum multiplication depth needed for your specific circuit
• Choose the smallest parameters providing sufficient noise budget (with safety margin)
• Significantly more efficient than fully unlimited FHE -- often 10-100x faster
• Works well when the computation graph is known at compile time

Most practical FHE applications use leveled FHE with carefully planned computation depth. H33's authentication pipeline is a textbook example: the biometric matching circuit has a known, fixed structure (inner product of enrolled template against probe), so we can engineer parameters that are exactly sufficient. This is how a 32-user batch completes in roughly 1,109 microseconds -- the parameters are tight, not bloated for hypothetical deeper circuits.

Bootstrapping

Bootstrapping "refreshes" a ciphertext by homomorphically evaluating the decryption circuit. The idea, first proposed by Craig Gentry in 2009, is conceptually elegant: encrypt the secret key under a second key, then run decryption as a homomorphic computation. The output is a new ciphertext of the same plaintext but with fresh, minimal noise.

• Takes a noisy ciphertext approaching its noise ceiling
• Produces a fresh ciphertext with minimal noise, resetting the budget
• Enables unlimited computation depth (true FHE, not just leveled)
• Computationally expensive: typically 10-100 milliseconds per bootstrap

Bootstrapping is Gentry's breakthrough that made unlimited FHE theoretically possible, but its cost makes it a last resort in practice. For latency-sensitive applications like real-time authentication, bootstrapping is not viable. At ~42 microseconds per auth, H33's entire pipeline completes faster than a single bootstrap operation would take. This is precisely why leveled parameter selection matters -- you avoid bootstrapping entirely by ensuring the circuit never exhausts its noise budget.

Noise Management Strategies

Minimize Multiplication Depth

Restructure computations to reduce the longest chain of dependent multiplications. Tree-structured evaluation halves the depth compared to sequential chaining:

// Deep: a * b * c * d  (depth 3, noise: O(e^8))
// Shallow: (a * b) * (c * d)  (depth 2, noise: O(e^4))

// H33 inner product: sum of (template[i] * probe[i])
// Only depth 1 -- each multiply is plaintext * ciphertext,
// then all 128 products are accumulated via addition.
// Addition barely moves the noise needle.

Use SIMD Batching

Pack multiple values into polynomial slots and operate in parallel -- same noise cost, vastly more computation per ciphertext. H33 packs 32 users into a single ciphertext (4096 slots / 128 dimensions), meaning one FHE operation processes 32 authentications simultaneously. The noise growth is identical whether you fill one slot or all 4096.

Choose the Right Scheme

CKKS includes a built-in rescaling operation that truncates noise after multiplications, effectively managing noise as part of the scheme mechanics. BFV, which H33 uses for exact integer arithmetic on biometric templates, relies instead on modulus switching -- dropping the ciphertext modulus to proportionally reduce noise. For H33's single-depth circuit, no modulus switching is needed at all.

NTT-Domain Persistence

A subtler noise management technique is keeping ciphertexts in NTT (Number Theoretic Transform) domain between operations. Forward and inverse NTT transforms do not add noise, but they cost O(N log N) time. By storing enrolled templates in NTT form and performing pointwise multiplication directly, H33 eliminates redundant transforms -- saving two full NTT operations per modulus per multiply. This does not reduce noise directly, but it frees the latency budget to use parameters that provide more noise headroom.

Optimize the Circuit

Rewrite computations to prefer additions over multiplications whenever possible. Polynomial approximations of functions (used in CKKS for non-linear activations) should use low-degree minimax polynomials rather than naive Taylor series. For BFV integer circuits, bit-decomposition tricks can sometimes replace a multiplication with a sequence of less expensive rotations and additions.

Monitoring Noise in Development

During development, track noise levels to validate that your circuit stays within budget. Most FHE libraries expose a noise measurement function that reports remaining budget in bits:

// Most FHE libraries provide noise measurement
const budget = seal.measureNoiseBudget(ciphertext);
console.log(`Remaining noise budget: ${budget} bits`);

if (budget < 10) {
  console.warn('Low noise budget - decryption may fail');
}

// H33 production: invariant noise budget >= 8 bits
// after inner product of 128-dim vectors across 32 users.
// If budget drops below threshold, alert fires.

In production, you should not call noise measurement on every ciphertext (it is itself a non-trivial computation). Instead, validate noise bounds offline during parameter selection, then enforce them with periodic spot-checks and integration tests that run the full circuit on worst-case inputs.

Practical Implications for Production

Noise management is not a theoretical exercise -- it directly shapes application architecture:

• Plan your computation graph before implementation. Know the exact circuit depth and width. For authentication, this means defining the biometric matching algorithm (inner product, Euclidean distance, cosine similarity) and computing its multiplicative depth analytically.
• Test with adversarial inputs. Worst-case noise occurs when plaintext values maximize the error terms. Test with boundary values, not just random data.
• Build in safety margins. If your theoretical budget is 12 bits after the circuit, target parameters that give 20+ bits. The cost is marginal; the reliability gain is significant.
• Consider breaking complex computations into stages. If a single circuit would require depth-5 parameters, splitting it into two depth-2 stages with an intermediate decrypt/re-encrypt may be faster overall, even accounting for the round-trip.
• Pair FHE with complementary primitives. H33 combines BFV encryption with ZK proof verification (in-process DashMap lookups at 0.085 microseconds) and Dilithium post-quantum signatures for attestation. Each component handles what it does best -- FHE protects the biometric data, ZKPs verify computation integrity, and Dilithium provides quantum-resistant signing -- so the FHE circuit stays minimal and the noise stays manageable.

Understanding noise is the key to successful FHE deployment. It determines your parameters, constrains your circuit design, and ultimately sets the ceiling on throughput. Plan carefully, choose leveled parameters when your depth is bounded, and your encrypted computations will not just succeed -- they will run at production speed. H33 processes 32 biometric authentications per ciphertext batch in ~1,109 microseconds, entirely within noise budget, entirely post-quantum secure.