💻 computer science

Machine-Checked Cardinality Bounds for Masked Barrett Reduction: A 1-Bit Side-Channel Leakage Barrier in Post-Quantum Cryptographic Hardware

This paper presents a machine-checked proof in Lean 4 establishing a universal "1-Bit Barrier" for masked Barrett reduction in post-quantum cryptography, demonstrating that its internal wire maps have a preimage cardinality of at most two, thereby guaranteeing at most one bit of min-entropy loss and enabling the construction of secure Prime-Field PINI compositions for ML-KEM and ML-DSA.

Original authors: Ray Iskander, Khaled Kirah

Published 2026-04-28

📖 5 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: Protecting Digital Secrets

Imagine you are building a high-security vault (a computer chip) to store digital secrets. To make sure no one can steal the secrets by listening to the power consumption or electromagnetic waves (a "side-channel attack"), you use a technique called masking.

Think of masking like putting your secret number inside a box, then adding a random, shifting number to it before you show it to the world. If you do this perfectly, an eavesdropper sees only random noise and learns nothing about your secret.

This paper focuses on a specific, tricky part of the vault's locking mechanism called Barrett Reduction. In the world of Post-Quantum Cryptography (the new kind of math needed to stop future super-computers), this step is essential but messy. The authors wanted to know: If we use masking here, is the vault truly secure, or does a tiny crack let a little bit of information leak out?

The Problem: The "Two-Door" Trap

Most parts of the vault (like the "Butterfly" stages mentioned in the paper) are like a perfect hallway: for every secret you put in, there is exactly one random path it can take to the exit. It's a perfect 1-to-1 match.

However, Barrett Reduction is different. It has a "conditional" step. Imagine a hallway with a fork in the road:

Door A: If the secret is small, you go left.
Door B: If the secret is large, you go right.

The authors discovered that because of this fork, a single output value on the wire could be produced by two different random masks instead of just one.

The Fear: If an attacker sees the output, they might think, "Aha! It could have come from Mask A or Mask B. I've narrowed it down!"
The Reality: The authors proved that it can never be more than two. It is never three, four, or a hundred. It is strictly 0, 1, or 2.

The "1-Bit Barrier"

The paper calls this discovery the 1-Bit Barrier.

Here is the analogy:
Imagine you are guessing a password.

Perfect Security: You have 1,000,000 possible passwords, and the attacker has no idea which one it is.
The Barrett Leak: Because of the "Two-Door" effect, the attacker might realize, "It's either Password A or Password B." They have narrowed the field from 1,000,000 to just 2.

In math terms, narrowing a field down to 2 possibilities costs you exactly 1 bit of security (since $2^1 = 2$ ).

The Claim: The authors proved that Barrett Reduction never leaks more than this 1 bit. It is a "conservative" ceiling. In many cases, the leak is actually less than 1 bit because some outputs are impossible to reach (the "0" case), which is actually a good thing for security.

The "Machine-Checked" Promise

Why should we trust this? Usually, security proofs are written on paper and checked by humans, who can make mistakes.

The Paper's Approach: The authors used a computer program called Lean 4 to write the proof.
The Analogy: Instead of a human saying, "I think this bridge is safe," they built a robot that checked every single bolt, beam, and screw of the bridge's design logic. The robot reported "Zero Errors" (or "Zero sorry," in computer terms).
The Result: This isn't just a theory; it is a mathematically verified certificate that works for any modulus (any size of secret number) used in current standards like ML-KEM and ML-DSA.

Why the "Adams Bridge" Chip Failed

The paper also explains why a specific chip design called Adams Bridge was found to be vulnerable in previous studies.

The Mistake: The chip designers put a fresh random mask between the "Butterfly" stages (the safe hallways) but forgot to put a fresh mask between the "Barrett" stages (the tricky two-door rooms).
The Consequence: Without that fresh mask, the small 1-bit leaks from the Barrett stages could stack up and multiply, turning a tiny crack into a massive hole.
The Lesson: The paper proves that if you do put fresh masks between every stage, the 1-bit barrier holds, and the whole system stays secure.

Summary of Findings

The Trichotomy: The math behind Barrett reduction is surprisingly simple. For any output, the number of ways to get there is always 0, 1, or 2. Never more.
The 1-Bit Limit: This means the maximum information an attacker can steal from a single wire in this process is 1 bit.
The Proof: This has been verified by a computer proof assistant (Lean 4) with zero errors, making it a gold-standard guarantee for hardware designers.
The Fix: To keep the whole system secure, hardware designers must ensure they refresh the random masks between every stage of the calculation. If they do, the "1-Bit Barrier" protects the entire pipeline.

In short: The authors found a tiny, unavoidable crack in the math of a specific encryption step, proved exactly how big that crack is (no bigger than 1 bit), and showed how to seal the rest of the vault so the crack doesn't matter.

1. Problem Statement

Post-Quantum Cryptography (PQC) standards like ML-KEM (FIPS 203) and ML-DSA (FIPS 204) rely heavily on Number Theoretic Transform (NTT) pipelines. These pipelines consist of linear "butterfly" stages and nonlinear modular reduction stages, typically implemented using Barrett reduction.

While existing formal verification frameworks (ISW, t-SNI, PINI, DOM) provide strong guarantees for Boolean masking over $GF(2)$, they lack machine-checked characterizations for arithmetic masking over prime fields ( $\mathbb{Z}_q$ ), specifically for Barrett reduction.

The Gap: Hardware implementations (e.g., the "Adams Bridge" design) often suffer from side-channel vulnerabilities because the nonlinear conditional subtraction in Barrett reduction breaks the affine structure assumed by standard composition theorems.
The Question: Under first-order arithmetic masking, what is the precise leakage bound of the internal wires of a Barrett reduction circuit? Previous tools could not provide a universal, machine-checked answer, leading to uncertainty in FIPS 140-3 certification.

2. Methodology

The authors employ a formal verification approach using the Lean 4 proof assistant and the Mathlib library.

Formalization: They define the Barrett internal wire map algebraically over $\mathbb{Z}_q$ (where $q$ is the modulus). The map $f_x(m)$ takes a secret $x$ and a random mask $m$ , producing an output based on a two-branch structure determined by a conditional subtraction.
Proof Strategy: Instead of simulating specific instances, they prove universal theorems that hold for all $q > 0$ and shift parameters $s$ .
Key Concept: They analyze the preimage cardinality: for a fixed secret $x$ and a specific output value $v$ , how many distinct masks $m$ could have produced $v$ ?
Toolchain: The artifact contains 12 proved results with zero sorry (no incomplete proofs), ensuring every step is kernel-verified by Lean.

3. Key Contributions

A. The Trichotomy Theorem

The paper proves that the Barrett internal wire map exhibits a three-valued preimage structure. For any secret $x$ and any output $v$ , the number of masks $m$ such that $f_x(m) = v$ is exactly 0, 1, or 2.

Mechanism: The conditional subtraction creates two affine branches (translations in $\mathbb{Z}_q$ ). The preimage of any value is a subset of at most two candidates: $\{x - v, x - v + r\}$ , where $r = 2^s \mod q$ .
Universality: This holds for any modulus $q$ and shift $s$ , independent of specific PQC parameters.

B. The 1-Bit Barrier

Based on the trichotomy, the authors establish a universal leakage bound:

Max-Multiplicity: Since the maximum number of masks producing a single output is 2, the maximum probability of observing a specific output value is $2/q$ .
Min-Entropy Bound: The conditional min-entropy $H_\infty(\text{output} \mid x)$ is bounded below by $\log_2(q) - 1$ .
Interpretation: Barrett reduction leaks at most 1 bit of min-entropy per internal wire under first-order probing. This is a "conservative" bound because many output values are unreachable (preimage count = 0), meaning actual leakage is often strictly less than 1 bit.

C. The PF-PINI Framework

The authors introduce Prime-Field PINI (PF-PINI), a new security metric for arithmetic gadgets over $\mathbb{Z}_q$ :

Definition: A gadget is PF-PINI( $k$ ) if the preimage cardinality is bounded by $k$ .
Instantiations:
- Butterfly Stages: Satisfy PF-PINI(1) (perfect bijection, zero leakage beyond the mask).
- Barrett Reduction: Satisfies PF-PINI(2) (the 1-Bit Barrier).
Composition Observation: They observe (though not yet formally proved) that if pipeline stages are separated by fresh inter-stage masking, the composed pipeline's max-multiplicity is $\max(k_1, k_2)$ . This implies the 1-Bit Barrier propagates through the entire NTT pipeline.

4. Results and Analysis

Machine-Checked Proofs: The artifact includes 12 verified theorems, including the trichotomy, tightness proofs (showing count=2 is achievable), and PF-PINI instantiations.
Support Gap Discovery: The analysis reveals "unreachable" output values (preimage count = 0). This is a security feature, not a bug, as it reduces the adversary's effective information.
Adams Bridge Case Study: The paper analyzes the "Adams Bridge" hardware implementation:
- Intra-stage failure: Previous work (Papers 1 & 2) showed vulnerabilities due to share interaction without intermediate masking.
- Inter-stage failure: This paper identifies that Adams Bridge fails to apply fresh masking between stages. Consequently, the PF-PINI composition bound does not apply, allowing leakage to multiply ( $k_1 \times k_2$ ) rather than remain bounded by the maximum ( $\max(k_1, k_2)$ ). This explains why the design is vulnerable despite the 1-Bit Barrier existing for individual Barrett gates.
Quantitative Impact:
- For ML-KEM ( $q=3329$ ): Leakage $\le 1$ bit (Min-entropy $\ge 10.70$ bits).
- For ML-DSA ( $q=8,380,417$ ): Leakage $\le 1$ bit (Min-entropy $\ge 21.99$ bits).

5. Significance

Certification Readiness: The 1-Bit Barrier provides a universal, machine-checked certificate for hardware designers. It allows evaluators to certify Barrett-based implementations for FIPS 140-3 without re-verifying specific parameter sets.
Design Guidance: It clarifies that the primary architectural requirement for security is fresh inter-stage masking. If this is implemented, the nonlinear nature of Barrett reduction does not compromise the security of the NTT pipeline beyond a negligible 1-bit loss.
Methodological Shift: The paper moves side-channel analysis from empirical simulation and SAT-based checking to kernel-verified algebraic proofs, setting a new standard for PQC hardware verification.
Completing the Five-Paper Program: This work closes the gap left by previous papers in the series, moving from tool construction (Paper 1) and attack quantification (Paper 2) to algebraic foundations (Paper 3), linear composition (Paper 4), and finally, nonlinear characterization (Paper 5).

6. Limitations and Future Work

Composition Proof: The claim that $\max(k_1, k_2)$ holds for composed pipelines with fresh masking is currently an observation, not a formal theorem.
Higher-Order Masking: The results are limited to first-order masking ( $t=1$ ). Higher-order security requires analyzing joint preimages across multiple wires.
Entropy Formalization: While the algebraic bound is proven, the information-theoretic min-entropy bound relies on standard definitions not yet fully upstreamed into Mathlib.
Other Reductions: The results are specific to Barrett reduction; Montgomery and schoolbook reductions require separate analysis.

In summary, this paper establishes that Barrett reduction is fundamentally secure under first-order arithmetic masking, leaking no more than 1 bit of information per wire, provided that fresh masking is applied between pipeline stages. This provides a rigorous mathematical foundation for securing next-generation PQC hardware.