Accurate BGV Parameters Selection: Accounting for Secret and Public Key Dependencies in Average-Case Analysis

Here is an explanation of the paper "Accurate BGV Parameters Selection" using simple language, analogies, and metaphors.

The Big Picture: The "Noisy Envelope" Problem

Imagine you have a Fully Homomorphic Encryption (FHE) scheme. Think of this as a magical, unbreakable glass envelope.

You put a secret letter inside (the plaintext).
You seal it with a special lock (the ciphertext).
The magic is that you can shake, squeeze, and even multiply the envelope while it's locked, and the letter inside changes accordingly. When you finally unlock it, the letter has been processed, but no one ever saw the content.

However, there is a catch: Noise.

Every time you perform a math operation (like multiplication) on the sealed envelope, a little bit of static noise gets added to the letter inside.

Addition adds a tiny bit of static.
Multiplication adds a lot of static.

If the static gets too loud, it drowns out the message. When you try to open the envelope at the end, you can't read the letter anymore. The envelope has "failed."

To prevent this, the envelope must be made of a specific size of material (called the modulus, or $q$ ). A bigger envelope can hold more static before it breaks. But making the envelope too big is expensive (slow and heavy). Making it too small causes the message to get lost.

The Goal of this Paper: The authors want to find the perfect size for the envelope. They want it to be just big enough to survive the journey, but not so big that it wastes energy.

The Old Way: Guessing and Over-Protecting

For a long time, scientists estimated how much noise would grow using a "Worst-Case" approach.

The Analogy: Imagine you are packing for a trip. A "Worst-Case" planner assumes it will rain, snow, hail, and the bus will break down. So, they pack a tent, a snowsuit, a raincoat, and a spare tire.
The Result: You arrive safely, but you are carrying 50 pounds of gear you didn't need. In encryption terms, this means the "envelope" ( $q$ ) is made unnecessarily huge, making the system slow and inefficient.

Later, researchers tried an "Average-Case" approach.

The Analogy: They looked at the weather forecast and said, "It's usually sunny, maybe a light drizzle." So, they packed a light jacket.
The Problem: They assumed the raindrops fall independently. They didn't realize that sometimes, the raindrops clump together in heavy storms. Because they ignored these "clumps" (dependencies), their light jacket wasn't enough, and the message got wet (decryption failed).

The New Discovery: The "Family Connection"

The authors of this paper discovered something crucial that previous methods missed: The noise isn't random strangers; it's a family.

In the BGV encryption scheme, every time you create a new envelope, you use the same Secret Key (like a master key) and the same Public Key (like a standard stamp).

Because the same keys are used for every operation, the noise generated in different envelopes shares common "DNA."
When you multiply two envelopes, their noise doesn't just add up; it interacts because they share these common key components.

The Metaphor:
Imagine two musicians playing a song.

Old View: We thought they were playing in different rooms. We just added the volume of Room A to the volume of Room B.
New View: The authors realized they are in the same room, playing the same instrument with the same sheet music. When they play together, the sound waves interfere and amplify each other in specific ways. You can't just add the volumes; you have to account for the harmony (or dissonance) between them.

The Solution: The "Correction Function"

The authors created a new mathematical tool called a Correction Function.

Think of this as a smart calculator that knows exactly how much the "family connection" (the shared keys) will amplify the noise.
Instead of guessing or assuming the noise is independent, this calculator says: "Because these two envelopes used the same secret key, the noise will grow by a factor of 2 (or another specific number), not just 1."

By using this precise calculator, they can predict exactly how big the envelope needs to be.

The "Modulus Switching" Safety Net

The paper also confirms a vital safety rule: Modulus Switching.

The Analogy: Imagine you are carrying a heavy box (the noise) up a flight of stairs. If you keep carrying it, it gets too heavy.
Modulus Switching: Every few steps, you swap the heavy box for a slightly lighter one that still contains the same message. This resets the noise level.
The Finding: The authors proved that if you do this "swap" correctly, the noise behaves nicely (like a bell curve/Gaussian distribution). If you don't do this swap, the noise becomes chaotic and unpredictable (heavy-tailed), and your safety calculations fail.

Why This Matters (The Results)

By using their new method:

Safety: They never underestimate the noise. The envelope is guaranteed to be big enough to hold the message.
Efficiency: Because they don't over-pack (unlike the "Worst-Case" method), the envelopes are significantly smaller.
- In their tests, they reduced the size of the encryption parameters by about 15-20% compared to popular libraries like OpenFHE.
- Real-world impact: This means faster calculations, less memory usage, and lower costs for running secure AI or private data analysis in the cloud.

Summary in One Sentence

The authors found that encryption noise acts like a family with shared traits rather than random strangers; by mathematically accounting for these family ties, they can build smaller, faster, and safer digital envelopes for secret data.

Here is a detailed technical summary of the paper "Accurate BGV Parameters Selection: Accounting for Secret and Public Key Dependencies in Average-Case Analysis."

1. Problem Statement

The Brakerski-Gentry-Vaikuntanathan (BGV) scheme is a leading Fully Homomorphic Encryption (FHE) system based on the Ring Learning with Errors (RLWE) problem. A critical challenge in BGV is managing noise growth during homomorphic operations. If the noise exceeds a specific threshold relative to the ciphertext modulus ( $q$ ), decryption fails.

The Trade-off: To support deeper circuits, $q$ must be large. However, larger $q$ reduces efficiency and can compromise security.
The Gap: Current parameter selection methods often rely on worst-case analysis (using norms like infinity or canonical), which leads to overly conservative (large) moduli, or average-case analysis that assumes noise coefficients are independent.
The Flaw: Recent critiques (e.g., [24]) suggest that standard average-case assumptions fail because noise coefficients can exhibit heavy-tailed distributions, particularly when modulus switching is omitted. Furthermore, existing average-case methods often underestimate noise growth by ignoring dependencies between error terms introduced by shared secret ( $s$ ) and public ( $e$ ) keys. This underestimation risks decryption failures and security vulnerabilities.

2. Methodology

The authors propose a novel average-case noise analysis that explicitly models the statistical dependencies between noise coefficients caused by the reuse of secret and public keys.

A. Modeling Dependencies

The core insight is that when two ciphertexts (computed with the same key) are multiplied, their noise terms share common factors involving powers of the secret key ( $s$ ) and error terms ( $e$ ).

The critical quantity $\nu$ is decomposed into terms involving $s^\iota$ and $e^\mu$ .
The authors define a Correction Function ( $F$ ) derived from formal probability theory (specifically Isserlis' Theorem) to adjust the variance calculation of the product of two polynomials.
Unlike previous heuristic approaches (e.g., in BFV analysis), this correction function is mathematically derived to account for:
1. Secret Key Dependencies: Powers of $s$ appearing in the product.
2. Public Key Dependencies: Powers of $e$ (error) appearing in the product.

B. Validating Gaussianity

A prerequisite for average-case analysis is that noise coefficients follow a Gaussian distribution.

The paper addresses the critique that noise can be heavy-tailed.
Key Finding: The authors prove that while noise may be heavy-tailed without modulus switching, the application of modulus switching (standard in BGV libraries) forces the dominant error terms to converge to a Gaussian distribution via the Central Limit Theorem.
They establish a condition (Equation 12) on the size of the moduli primes ( $p_\ell$ ) to ensure the Gaussian assumption holds, preventing decryption failures.

C. Variance Estimation in Circuits

The authors derive a recursive formula to estimate noise variance ( $V_\ell$ ) at each level of a circuit:

Fresh Encryption: Calculate initial variance based on $s$ and $e$ distributions.
Modulus Switching: Model the reduction in variance and the addition of new noise from the switching process.
Multiplication: Apply the correction function $F_s$ $F_{s}$ (for secret key) and $F_e$ $F_{e}$ (for public key) to the product of variances.
- Result: The variance after multiplication is approximately **$2n V_{ms}^2 $** (where$ V_{ms} $is the variance after modulus switching), whereas naive independent models would estimate$ n V_{ms}^2$. The factor of 2 arises from the dependencies.

3. Key Contributions

Dependency-Aware Average-Case Analysis: The first average-case analysis for BGV that rigorously accounts for dependencies between error coefficients induced by both the secret and public keys, eliminating the underestimation found in prior works.
Formal Correction Function: Introduction of a non-heuristic correction function $F$ derived from Isserlis' Theorem, providing tight probabilistic upper bounds on noise growth.
Gaussianity Proof with Modulus Switching: Rigorous theoretical and empirical proof that modulus switching ensures noise coefficients follow a Gaussian distribution, validating the use of average-case analysis in practical BGV implementations.
Library-Independent Framework: A general method for parameter selection that does not rely on specific library implementations (unlike previous HElib-specific analyses), making it applicable to OpenFHE, HElib, and others.

4. Results

The authors validated their method using the OpenFHE library with ring dimensions $n \in \{2^{12}, \dots, 2^{15}\}$ .

Accuracy: The theoretical variance estimates matched experimental data with high precision (e.g., for $n=2^{13}$ , theoretical log-variance was 95.68 vs. experimental 95.65). Crucially, the estimates never underestimated the experimental noise.
Modulus Reduction: By using tighter bounds, the authors demonstrated significant reductions in the required ciphertext modulus size ( $q$ $q$ ) compared to state-of-the-art libraries:
- OpenFHE Comparison: For a multiplicative depth of 6 and $n=2^{13}$ , their method reduced $\log_2(q)$ from 256.8 bits (OpenFHE) to 216.8 bits (a reduction of ~40 bits).
- HElib Comparison: Their method allows for smaller primes between modulus levels (reducing the ratio by up to 6 bits), leading to smaller overall modulus chains.
Security: The method maintains the required security level (128-bit) while improving efficiency, as the tighter bounds prevent the "safety margin" inflation seen in worst-case analyses.

5. Significance

Efficiency: The reduction in ciphertext modulus size directly translates to faster homomorphic operations and lower memory usage, making FHE more practical for real-world applications.
Reliability: By correcting the underestimation of noise, the method prevents decryption failures that could occur if parameters were chosen based on flawed independent-noise assumptions.
Theoretical Foundation: The work bridges the gap between theoretical worst-case bounds and practical average-case performance, providing a robust mathematical framework for future FHE parameter selection.
Adoption: The findings support the widespread adoption of average-case analysis in FHE libraries, provided that modulus switching is used and specific prime size constraints are met to ensure Gaussianity.

In summary, this paper provides a mathematically rigorous, dependency-aware framework for selecting BGV parameters that is both safer (no underestimation of noise) and more efficient (smaller moduli) than current industry standards.