💻 computer science

Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption

This paper presents a machine-checked proof using Rocq and SSProve that establishes a tight, square-root security bound for noise flooding in homomorphic encryption against adaptive decryption attacks by introducing a new relational program logic with a Pythagorean judgment that composes conditional KL costs without intermediate conversion to statistical distance.

Original authors: Yi Lee, Alexandru Cojocaru, Junyi Liu, Xiaodi Wu

Published 2026-08-17

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Yi Lee, Alexandru Cojocaru, Junyi Liu, Xiaodi Wu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are sending a secret message to a friend, but you have to send it through a post office run by a mischievous goblin who loves to peek at letters. In the old days, you'd lock the letter in a box, but once the goblin opened it to read the message, the secret was gone. Then, a magical invention called Homomorphic Encryption arrived. This is like a special lockbox that lets the goblin do math on the locked letters—adding them, multiplying them, sorting them—without ever unlocking them. When the goblin hands the result back, you unlock it, and it's the correct answer to the math problem, even though the goblin never saw the numbers inside.

However, there's a catch. In the most popular version of this magic, called CKKS, the math isn't perfect. Because the numbers are so complex, the result you get back is slightly "fuzzy" or approximate, like a blurry photo instead of a sharp one. Usually, this fuzziness is fine; it's just a tiny bit of static. But a sneaky goblin (an attacker) can ask for the answer to many different math problems, compare the blurry results with what they think the answer should be, and use those tiny differences to slowly reconstruct your secret key. It's like if the goblin could tell exactly how much your lockbox wobbled when you shook it, and used that wobble to figure out the combination. To stop this, cryptographers came up with a defense called Noise Flooding: they add a giant, random burst of static (noise) to the answer before sending it back, drowning out the tiny clues the goblin was trying to use.

The big question was: How much static do you need to add? If you add too little, the goblin can still hear the secret. If you add too much, the answer becomes so blurry it's useless. The tricky part is that the goblin can ask questions one by one, changing their strategy based on your previous answers. If you add static for each question separately, the "cost" of the static adds up quickly, forcing you to make the answers incredibly blurry. But a clever mathematical idea suggested that if you look at the whole game at once, the cost might grow much slower—like the square root of the number of questions, rather than the number itself. This paper is about proving that this clever idea actually works, and proving it in a way that a computer can check every single step to make sure no mistakes were made.

The Paper's Big Discovery: The "Pythagorean" Secret

This paper, titled "Verified Pythagorean Composition for Adaptive Cryptographic Games," is a massive achievement in formal verification, which is basically using a super-smart computer to check math proofs for errors. The authors, a team of researchers, took a famous security argument about noise flooding and translated it into a language the computer could understand. They then asked the computer to verify every single logical step, ensuring that the math holds up under the most intense scrutiny.

The core of their work is a new way of thinking about how errors add up when you have a sneaky attacker asking many questions.

The "Blurry Photo" Problem

Imagine you are trying to hide a secret by adding a little bit of static to a photo. If you add a tiny bit of static, the photo is still clear, but a sharp-eyed goblin might spot the secret. If you add a lot of static, the secret is safe, but the photo is now a mess.
In the world of encryption, the "static" is called noise. The paper looks at a scenario where an attacker asks for the decrypted result of a message up to $q$ times. Each time, the defender adds noise to hide the secret.

The Old Way (Linear Loss): If you treat each question as a separate event, you have to add enough noise to be safe for every single question. If the attacker asks 100 questions, you might need 100 times the noise, making the final result completely useless.
The New Way (Square-Root Loss): The paper confirms a smarter strategy. It shows that because the attacker's questions are connected (they are "adaptive"), the total amount of noise needed only grows by the square root of the number of questions ( $\sqrt{q}$ ). So, for 100 questions, you only need 10 times the noise, not 100. This is a huge win because it means you can keep the answers much clearer while still being safe.

The "Pythagorean" Analogy

Why do they call it "Pythagorean"? Think of a right-angled triangle. If you have two sides of length 3 and 4, the longest side (the hypotenuse) isn't $3 + 4 = 7$ . It's $\sqrt{3^2 + 4^2} = 5$ . The total length is shorter than just adding the sides up.
In this paper, the "sides" are the tiny bits of risk (or "cost") from each of the attacker's questions.

The Mistake: If you just add the risks together ( $3 + 4$ ), you get a huge, scary number.
The Reality: The authors prove that these risks combine like the sides of a triangle. They "cancel out" a bit because they are related. The total risk is the square root of the sum of the squares.
The paper proves that you can keep track of these risks separately (as "Conditional Kullback-Leibler costs," which is a fancy math way of saying "how different the answers look") and only convert them into a final "safety score" at the very end. This allows the math to stay efficient and the noise to stay low.

The Computer's Role: The "Robot Lawyer"

You might wonder, "Why do we need a computer to check this? Isn't math just math?"
The problem is that these proofs are incredibly complex. They involve thousands of steps, dealing with probabilities, random numbers, and the behavior of a sneaky attacker who changes their mind. It's easy for a human to miss a tiny detail or make a small assumption that breaks the whole argument.
The authors used a tool called Rocq (a proof assistant) and a library called SSProve. They didn't just write the proof on paper; they built a digital model of the encryption game.

The Logic: They created a new set of rules (a "program logic") that tells the computer how to handle these "Pythagorean" risk combinations.
The Compiler: They built a "trace compiler," which is like a robot that watches the attacker's program. It can pause the attacker, peek at their next move, and then let them continue, all while keeping the secret safe.
The Verification: The computer checked every single line of code and every mathematical step. It confirmed that if the underlying encryption is secure, then adding this noise flooding defense makes it secure against these specific types of attacks, with the "square-root" efficiency.

What This Means for You

The paper doesn't invent a new encryption method or a new attack. Instead, it takes a known defense (noise flooding) and proves, with absolute mathematical certainty, that it works exactly as the clever "Pythagorean" theory predicted.

It rules out the idea that you need to add a massive amount of noise (linear growth) to stay safe against adaptive attackers.
It proves that the "square-root" growth is real and safe, provided the underlying encryption is already secure.
It confirms that the complex math behind this defense doesn't have hidden holes.

The authors are very careful to say that this is a verified proof of the logic, not a guarantee that every specific encryption software in the world is perfect. They proved that if you have a good encryption scheme and you apply this noise flooding correctly, the math says you are safe. They also noted that they didn't check the specific details of the most popular encryption scheme (CKKS) itself, just the logic of the noise defense. But for the defenders of digital privacy, this is a massive step forward: it means we can trust the math that keeps our secrets safe, even when the attackers are smart and persistent.

In short, the paper is like a master architect who, after years of debate, finally brings in a team of robot inspectors to confirm that the bridge's design is sound. They proved that the bridge doesn't need to be built with twice as much steel as we thought; the clever geometry of the design (the Pythagorean rule) is enough to hold the weight, keeping the path clear and the secrets hidden.

Technical Summary: Verified Pythagorean Composition for Adaptive Cryptographic Games

Problem Statement
Approximate Homomorphic Encryption (FHE), particularly the CKKS scheme, allows computation on encrypted data but introduces small, controlled errors. While this is acceptable for many applications, it creates a vulnerability: an attacker with knowledge of inputs and the computation can predict the exact mathematical result and compare it against the decrypted approximate output. Li and Micciancio demonstrated that these discrepancies can leak the secret key. To counter this, Li, Micciancio, Schultz-Wu, and Sorrell (LMSS) proposed "noise flooding," a defense that adds fresh, wide Gaussian noise to decrypted results.

The core challenge addressed in this paper is the composition of security proofs for adaptive adversaries. In an adaptive setting, an attacker makes up to $q$ decryption queries, choosing each based on previous answers. Standard security proofs often replace real oracle answers with simulated ones and apply Pinsker's inequality to bound the statistical distance. However, applying this conversion at every step results in a linear loss in $q$ (i.e., $q \times \epsilon$ ), requiring the noise width to grow linearly with the number of queries, which destroys numerical precision.

The LMSS argument utilizes a "Pythagorean" composition principle: instead of converting conditional Kullback–Leibler (KL) divergence to statistical distance at every step, the proof accumulates the KL costs and applies Pinsker's inequality only once at the end. This yields a square-root loss ( $\sqrt{q} \times \epsilon$ ), preserving precision. While mathematically concise on paper, this argument involves complex interactions between probability theory, adaptive program semantics, and game-based reductions, making it prone to subtle errors that are difficult to detect manually.

Methodology
The authors employ a machine-checked formalization using the Rocq proof assistant and the SSProve library for cryptographic games. Their methodology involves two distinct levels of verification:

Cryptographic Level: They formalize the LMSS reduction, defining the IND-CPA and IND-CPAD security games, the noise-flooded construction, and the specific reduction steps. They verify that the security of the noise-flooded scheme reduces to the underlying IND-CPA security plus a quantified statistical loss.
Program Logic Level: To handle the adaptive nature of the adversary (where queries are not a fixed list but depend on state), they develop a new Pythagorean relational program logic.
- Pythagorean Judgment: Unlike standard additive-error logics that sum errors linearly, this judgment records a tuple of conditional KL costs. It allows the sequencing of program fragments to concatenate these tuples without converting them to statistical distance.
- Verified Selected-Call Compiler: Since SSProve adversaries are stateful programs rather than syntactic lists of calls, the authors built a verified compiler. This tool "exposes" the first $q$ calls to a specific operation within an arbitrary adaptive program, replacing them with a chosen implementation while preserving the surrounding control flow and state invariants.
- Bridge to Statistical Distance: A verified rule (based on Micciancio and Walter) converts the accumulated tuple of KL costs into a single additive statistical distance bound only after the full adaptive transcript is constructed.

Key Contributions

Verified Noise-Flooding Reduction: The paper presents a machine-checked proof that an IND-CPA secure and approximately correct FHE scheme, when transformed with noise flooding, achieves IND-CPAD security. The proof establishes the bound:
$\text{WinProb}[\text{IND-CPAD}] \leq \beta_{\text{CPA}} + \frac{\sqrt{qn}}{2\gamma}$
where $n$ is the plaintext dimension, $\gamma$ is the flooding-width multiplier, and $\beta_{\text{CPA}}$ is the underlying scheme's advantage.
Reusable Pythagorean Program Logic: The authors define and verify a new relational logic that accumulates conditional KL budgets. This logic separates the accumulation of costs from their conversion to statistical distance, enabling sublinear ( $\sqrt{q}$ ) security bounds for adaptive programs.
Verified Selected-Call Compiler: They construct a trace-based compiler that lifts local oracle replacement rules to arbitrary adaptive programs. This compiler ensures that replacing specific calls in a stateful program preserves semantic behavior when the same implementation is used for both selected and residual calls.
Probability Formalization: The work includes a formal verification of discrete Gaussian properties, KL divergence bounds, Pinsker's inequality, and the conditional-coordinate chain rule, ensuring the mathematical foundations are rigorous within the proof assistant.

Results
The formalization successfully verifies the LMSS argument, confirming that the square-root composition loss is valid under the stated assumptions. The proof constructs an explicit IND-CPA adversary $B_{A,q}$ and demonstrates that the winning probability of any IND-CPAD adversary $A$ is bounded by the underlying IND-CPA advantage plus the derived square-root term. The development consists of approximately 28,000 lines of Rocq code, organized into reusable layers for probability, logic, and compiler machinery, and an application-specific layer for noise flooding.

Significance and Claims
The paper claims to provide the first machine-checked verification of the Pythagorean composition principle in the context of adaptive cryptographic games. By isolating the "good-execution" step of the LMSS argument, the authors verify that the security loss scales with $\sqrt{q}$ rather than $q$ , which is critical for maintaining the utility of decrypted results in approximate FHE.

The authors explicitly state that they do not claim a verified deployment of a specific CKKS instantiation or concrete parameter sets. Their work assumes the underlying scheme is IND-CPA secure and approximately correct with probability one, and that the message space satisfies specific coordinate chart properties. They note that formalizing the "up-to-bad" game hops required for imperfect correctness (e.g., handling bad key pairs in CKKS) remains a future task.

The significance lies in the modularity and reusability of their machinery. The Pythagorean logic and selected-call compiler are independent of FHE and can be applied to other adaptive cryptographic proofs, such as comparing ideal samplers with finite-precision implementations or analyzing threshold protocols. The work demonstrates that complex, parameter-sensitive composition arguments in cryptography can be rigorously verified, reducing the risk of subtle errors in security proofs that rely on non-linear composition of probabilistic bounds.