💻 computer science

Fresh Masking Makes NTT Pipelines Composable: Machine-Checked Proofs for Arithmetic Masking in PQC Hardware

This paper presents the first machine-checked proofs in Lean 4 demonstrating that fresh per-stage arithmetic masking guarantees pipeline-level security for Number Theoretic Transform (NTT) accelerators in post-quantum cryptography, while identifying specific architectural failures like the Adams Bridge accelerator that violate these security conditions.

Original authors: Ray Iskander, Khaled Kirah

Published 2026-04-23

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ray Iskander, Khaled Kirah

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

The Big Picture: Building a Secure Digital Vault

Imagine you are building a high-security vault to protect a secret (like a password or a private key). In the world of "Post-Quantum Cryptography" (the new kind of math used to stop future quantum computers from stealing secrets), this vault is built using a complex machine called an NTT Pipeline.

Think of this pipeline as a factory assembly line. Raw materials (your secret data) go in one end, pass through a series of workstations (stages), and come out the other end as a finished product.

The problem? Thieves (hackers) are trying to sneak a peek at the materials while they are being processed. To stop them, the factory uses a technique called "Masking."

The Analogy: The "Confetti" Strategy

Imagine you are carrying a stack of important papers (your secret) through a crowded room.

Without Masking: You carry the papers openly. Anyone can read them.
With Masking: You put the papers inside a box, but the box is transparent. To hide the papers, you throw a handful of confetti (random numbers) over them.
- The papers are still there, but now they are mixed with confetti.
- To a thief looking at just one spot, they see a jumble of paper and confetti. They can't tell what the original paper said.
- The Rule: To be truly secure, you must throw fresh, new confetti at every single workstation on the assembly line.

The Problem: The "Intuition Trap"

The engineers building these factories have a strong intuition: "If every single workstation is secure on its own, then the whole assembly line must be secure."

For a long time, nobody could prove this mathematically for these specific machines.

The Trap: Engineers tried to check security by asking, "If I change the secret paper, does the confetti-covered pile look different?"
The Surprise: The authors of this paper proved that for these specific machines, the answer is YES, the pile does look different if you change the secret.
The False Alarm: If an engineer saw this, they would panic and think, "Oh no! The machine is broken! It's leaking secrets!" They would throw away a perfectly good design.
The Reality: The machine is actually fine. The "different look" is just a mathematical illusion caused by how the math works. The real test isn't "does it look different?" but "is the confetti distribution random enough?"

The Three Big Discoveries

The authors used a super-smart computer assistant (called Lean 4) to write a "proof" that a human can't argue with. They found three things:

1. Fixing the "Missing Link"

In previous work, they proved that if the confetti is random, the secret is safe. But they had a small gap in the proof: they hadn't fully explained what happens when you add new confetti at every step.

The Fix: They plugged that hole. They proved that adding fresh randomness (new confetti) at every step guarantees that the "leakage" (what the thief sees) is completely independent of the secret.

2. The "One-to-One" Magic Trick

They looked at a single workstation (a "Butterfly" stage). They proved a magical property:

No matter what the secret is, and no matter what the other confetti is, there is exactly one specific amount of "fresh confetti" that will make the output look like any specific value.
The Metaphor: Imagine a lock. No matter what key you try, there is exactly one specific "jiggle" of the tumblers that opens it. Because there is always exactly one way to get any result, the thief sees a perfectly uniform distribution of possibilities. They learn nothing.
The Warning: They also proved that the "obvious" way to check security (looking at the raw numbers) is a trap. If you check that way, you will falsely accuse secure machines of being broken.

3. The "Fresh Masking" Rule for the Whole Line

This is the most important part. They proved that if you follow one simple rule, the entire assembly line is secure:

The Rule: Every single workstation must get its own fresh, independent handful of confetti.
The Result: If you do this, the security of the whole line is guaranteed. The "confetti" at the end is just as random as the "confetti" at the beginning.

The Villain: The "Adams Bridge" Machine

The paper uses this new proof to analyze a real-world machine called the Adams Bridge (used in a project called Caliptra).

What it did wrong: The Adams Bridge machine was lazy. It threw fresh confetti at the first workstation, but then it stopped. For the rest of the assembly line, it reused the same old confetti or used none at all.
The Consequence: Because it broke the "Fresh Masking Rule," the security guarantee vanished. The "confetti" started to pile up in a predictable way, allowing thieves to reconstruct the secret.
The Diagnosis: This paper explains why it failed. It wasn't just a bug; it was a fundamental architectural flaw. The machine tried to skip the "fresh confetti" step, and the math proved that you can't skip it.

Why Should You Care?

For Engineers: It gives them a "Gold Standard" proof. They can now say, "We followed the Fresh Masking Rule, and a computer has mathematically proven our design is safe." This helps them get certified by government standards (like FIPS).
For Everyone: It ensures that the digital locks protecting our future (banking, voting, communications) are actually strong. It stops engineers from accidentally building "fake secure" vaults that look good but fall apart under pressure.

Summary in One Sentence

This paper uses a super-computer to prove that if you throw a fresh handful of "random confetti" at every step of a secret-processing machine, the whole machine is mathematically unbreakable, and it exposes a real-world machine that failed because it stopped throwing confetti halfway through.

1. Problem Statement

Post-Quantum Cryptography (PQC) standards, specifically ML-KEM (FIPS 203) and ML-DSA (FIPS 204), rely heavily on the Number Theoretic Transform (NTT) implemented over finite rings $\mathbb{Z}_q$ . Hardware accelerators for these algorithms often use pipelined Cooley-Tukey butterfly stages.

While individual masking gadgets (like XOR or AND gates) have been formally verified for security, a critical gap exists in the composition of these gadgets in arithmetic pipelines:

The Gap: Existing machine-checked frameworks (ISW, t-SNI, PINI, DOM) are formalized primarily for Boolean masking over $GF(2)$. No formal proof exists for the composition of arithmetic masking over $\mathbb{Z}_q$ specifically for the NTT butterfly structure.
The Trap: Designers often intuitively assume that if each pipeline stage is secure, the whole pipeline is secure. However, the standard security property checked by designers—pointwise value-independence (where a wire's value does not change if the secret changes while masks are fixed)—is false for NTT butterflies. Relying on this false property leads to incorrect security conclusions.
Real-World Impact: The Adams Bridge accelerator (used in CHIPS Alliance Caliptra) was found empirically insecure in prior work. The root cause was suspected to be a lack of fresh masking between stages, but a formal mathematical explanation was missing.

2. Methodology

The authors utilize Interactive Theorem Proving (ITP) to provide rigorous, machine-checked guarantees.

Toolchain: The proofs are formalized in Lean 4 using the Mathlib library.
Scope: The work covers the ISW first-order probing model, where an adversary can observe exactly one wire per clock cycle.
Approach:
1. Algebraic Modeling: The NTT butterfly is modeled as an affine function of the fresh mask.
2. Counter-Example Generation: Proving that the intuitive "pointwise value-independence" property fails.
3. Correct Property Definition: Defining and proving Butterfly Marginal Uniformity (the distribution of the output wire is uniform over the mask space, independent of the secret).
4. Inductive Composition: Proving that if each stage satisfies marginal uniformity and uses fresh, independent masks at every stage, the entire $k$ -stage pipeline maintains this property.

3. Key Contributions

The paper presents three primary machine-checked results (all with zero sorry, meaning no unverified axioms):

A. The $r$ -Bearing Bridge (Closing a Prior Limitation)

Context: Prior work (Paper 3) proved that value-independence implies constant marginal distribution but only for cases without fresh randomness ( $r$ -free).
Result: The authors extend this to the $r$ -bearing case (with fresh randomness). They prove that Value-Independence implies MutualInfoZero (zero mutual information between the secret and the wire) under fresh randomness. This bridges the gap between algebraic independence and information-theoretic security.

B. Butterfly Per-Context Uniformity (The Core Insight)

The Trap: The authors formally prove that Pointwise Value-Independence is false for butterfly outputs. Changing the secret does change the wire value even with fixed masks.
The Solution: They prove Butterfly Marginal Uniformity. For any Cooley-Tukey butterfly with a fresh output mask $m \in \mathbb{Z}_q$ $m \in Z_{q}$ :
- For any output wire and any target value $v$ , there is exactly one mask value $m$ that produces $v$ .
- This creates a uniform marginal distribution over the mask space, which is independent of the secret.
- Universality: This holds for all $q > 0$ (prime or composite), all twiddle factors, and all inputs.

C. Pipeline Composition (The Main Theorem)

Result: A $k$ -stage NTT pipeline with fresh per-stage masking satisfies per-context uniformity at every stage.
Mechanism: The proof relies on the fact that the butterfly is affine in the mask (similar to XOR in Boolean masking). Because the operation is linear/affine, the uniformity of the fresh mask propagates through the pipeline without accumulation of leakage, provided a new fresh mask is injected at every stage.
Significance: This establishes the Fresh Masking Design Principle: To secure an NTT pipeline, fresh independent masks must be applied at every stage boundary.

4. Results and Artifact Details

Formal Verification: The artifact consists of 9 theorems across 3 Lean 4 files (~580 lines of code).
Build Statistics: The formalization compiles with 1,738 build jobs, resulting in 0 errors and 0 warnings.
Case Study (Adams Bridge): The paper explains the architectural failure of the Adams Bridge accelerator.
- Adams Bridge applies masking only in Round 0 of the Inverse NTT (INTT).
- Subsequent rounds proceed unmasked.
- Conclusion: Because the "Fresh Masking Design Principle" (Theorem 6.2) is violated (no fresh masks in rounds 1–3), the composition theorem's guarantee does not apply, explaining the structural insecurity observed in prior empirical studies.

5. Significance and Impact

First Machine-Checked Proof for Arithmetic NTT: This is the first formal proof establishing the composition property for arithmetic masking in NTT pipelines over $\mathbb{Z}_q$ .
Correction of Design Heuristics: It explicitly warns hardware designers against checking "pointwise value-independence," which leads to false negatives (rejecting secure designs) or false positives (accepting insecure designs if they ignore the correct property).
FIPS Certification Support: The results provide a machine-checked, universally quantified proof that hardware designers can cite directly in FIPS 140-3 certification documentation to prove side-channel resistance.
Clarification of Scope: The paper clarifies that while the linear (affine) case is "easy" and solved here, the nonlinear case (Barrett reduction, masked multiplication) remains harder. The authors note that companion work (Paper 3/Reference [3]) addresses these nonlinear gadgets using a PF-PINI framework.

Summary of Limitations & Future Work

Linear Only: The current proof covers the affine butterfly. Nonlinear gadgets (Barrett reduction) are handled in separate work.
First-Order Only: The proof is for $t=1$ (first-order probing). Second-order security requires independent masks for every output pair, which is not covered here.
Idealized Model: The proof assumes a clean algebraic model. It does not account for glitch-extended models, transition leakage, or timing side channels (though QANARY, a separate tool, addresses structural dependencies in RTL).

In conclusion, this paper provides the mathematical and formal verification foundation required to securely implement PQC hardware accelerators, proving that fresh per-stage masking is the necessary and sufficient condition for the security of linear arithmetic NTT pipelines.