💻 computer science

Prime-Field PINI: Machine-Checked Composition Theorems for Post-Quantum NTT Masking

This paper presents the first machine-checked composition theorems for arithmetic masking over prime fields, proving that fresh random masking between pipeline stages ensures security independence from prior stages and using these formal results to diagnose a critical inter-stage masking flaw in Microsoft's Adams Bridge PQC accelerator.

Original authors: Ray Iskander, Khaled Kirah

Published 2026-04-29

📖 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

Imagine you are trying to send a secret message through a factory assembly line. The message is sensitive, so you don't want anyone watching the line to figure out what it is. To protect it, you break the message into pieces and mix each piece with a random "noise" (a mask) before it moves to the next station. This is called masking.

In the world of computer security, there are two main types of noise:

Boolean Noise: Like flipping switches (on/off). We already have a perfect rulebook for how to stack these switches safely.
Arithmetic Noise: Like adding numbers on a clock (where 12 + 1 = 1). This is what modern "Post-Quantum" cryptography uses. Until now, we didn't have a rulebook for stacking these number-based masks safely.

This paper provides that missing rulebook. Here is the story of what they found, explained simply.

1. The Problem: The "Leaky" Middle

Imagine a two-step factory line:

Station A: Takes your secret, adds some noise, and passes it along.
Station B: Takes what Station A passed, adds more noise, and sends the final result.

The researchers discovered a dangerous flaw in how these stations were connected in a famous Microsoft security chip (called "Adams Bridge").

In the flawed design, Station A passed its noisy result directly to Station B. Because of how the math works (specifically a step called "Barrett reduction," which is like a complex way of doing division), the "noise" coming out of Station A wasn't perfectly random. It had a pattern.

The Analogy: Imagine Station A is a blender. It mixes your secret with ice. But because of the way the blades spin, the ice chunks coming out are slightly uneven—some spots have more ice, some have less. If a spy (a hacker) stands right between Station A and Station B and counts the ice chunks, they can guess part of your secret. This is called a Side-Channel Attack.

2. The Solution: The "Fresh Mask" (The Renewal Argument)

The paper's big "Aha!" moment is surprisingly simple. They proved that if you insert a fresh, brand-new random mask between Station A and Station B, the problem disappears instantly.

The Analogy:

Without the fix: Station A hands a slightly uneven pile of ice to Station B. Station B tries to fix it, but the unevenness is already baked in.
With the fix: Station A hands its uneven pile to a "Reset Button." This button dumps the pile into a giant, perfectly mixed bucket of fresh water (the new mask). Now, when Station B takes a scoop from that bucket, it is perfectly random again.

The paper proves mathematically that this fresh mask completely erases the memory of Station A. It doesn't matter if Station A was messy or perfect; once the fresh mask is applied, the wire connecting to Station B is perfectly uniform. The security of the whole line then depends only on how good Station B is.

3. The "1-Bit Barrier"

The researchers found that for the specific math used in these chips (Barrett reduction), the noise is never perfectly random on its own. It has a "leak" of up to 1 bit of information.

Think of it like a coin that is slightly weighted. It's not a fair coin; it lands on "Heads" slightly more often.
This isn't a mistake in the design; it's a fundamental property of the math. The paper calls this the "1-Bit Barrier."
However, the paper proves that if you use the "Fresh Mask" trick between stages, that 1-bit leak is hidden inside the fresh noise and becomes useless to a spy.

4. The Proof: Machine-Checked

The authors didn't just write this down on paper; they used a computer program called Lean 4 to check every single step of their logic.

They wrote 18 specific proofs.
The computer verified them all with zero errors and zero "I'll do this later" notes (called "sorry stubs").
This means the math is rock-solid. It's not just a theory; it's a verified fact.

5. The Diagnosis: Why Microsoft's Chip Was Vulnerable

The team applied their new rulebook to Microsoft's "Adams Bridge" chip.

The Finding: The chip had two stages (Butterfly and Barrett) but no fresh mask between them.
The Result: The wire connecting these two stages was "leaky." It wasn't uniform. This confirmed why other researchers had already successfully hacked this chip using power analysis (measuring electricity usage).
The Fix: The paper prescribes a simple fix: Add one extra random number generator and one subtraction step between the stages. This makes the intermediate wire perfectly safe.

Summary

This paper solves a missing piece of the puzzle for secure computer chips.

The Problem: When chaining math operations together, the "noise" used to hide secrets can get messy and leak information in the middle.
The Fix: Insert a fresh, random "reset" between every step.
The Proof: They used a computer to prove that this reset makes the middle wire perfectly safe, regardless of how messy the first step was.
The Application: They showed exactly why a famous Microsoft chip was vulnerable and how to fix it with a simple architectural change.

In short: If you want to hide a secret through a multi-step process, don't just rely on the first step's disguise. Throw in a fresh disguise between every step, and the secret stays safe.

1. Problem Statement

The paper addresses a critical gap in the formal security verification of Post-Quantum Cryptography (PQC) hardware, specifically for Number Theoretic Transform (NTT) implementations used in NIST standards (ML-KEM and ML-DSA).

The Context: Hardware implementations of NTT rely on arithmetic masking over prime fields ( $\mathbb{Z}_q$ ) to resist side-channel attacks like Differential Power Analysis (DPA).
The Gap: While Boolean masking (over $GF(2^n)$ ) has a mature composition theory (NI, SNI, PINI) with machine-checked proofs, arithmetic masking over prime fields lacks analogous composition theorems.
The Specific Issue: In arithmetic masking, operations like modular reduction (e.g., Barrett reduction) interact with masks in non-trivial ways. Unlike Boolean XOR, where masking preserves uniformity perfectly, arithmetic masking can result in non-uniform output distributions (multiplicity > 1).
The Vulnerability: Previous empirical analyses and structural studies identified vulnerabilities in Microsoft's "Adams Bridge" PQC accelerator, where intermediate wires between pipeline stages were non-uniform, allowing DPA attacks. However, a formal theoretical explanation for why this happens and how to fix it via composition theorems was missing.

2. Methodology

The authors employ formal verification using the Lean 4 proof assistant to derive and prove composition theorems for arithmetic masking.

Formal Model: They define a quantitative security metric called PF-PINI(k) (Prime-Field Probe Isolating Non-Interference).
- Unlike binary security notions (secure/insecure), PF-PINI measures the multiplicity of output values relative to the mask space.
- $k=1$ implies a perfectly uniform distribution.
- $k=2$ implies a maximum multiplicity of 2, leaking up to 1 bit of information per wire.
The "Renewal Argument": The core theoretical insight is that applying a fresh random mask between two pipeline stages completely "erases" the security parameter ( $k_1$ ) of the first stage from the intermediate wire, regardless of how non-uniform the first stage's output was.
Hardware Bridging: The authors formally bridge the gap between abstract algebraic models ( $\mathbb{Z}_q$ ) and hardware-faithful natural number arithmetic (Nat) used in RTL designs, specifically for Barrett reduction.
Verification Scope: The entire work consists of 18 machine-checked theorems with zero sorry stubs (no unproven assumptions), ensuring high-assurance guarantees.

3. Key Contributions

The paper makes six primary contributions:

The Renewal Theorem (Theorem 4.1): Proves that if a fresh random mask is applied between two stages ( $G_1 \to G_2$ ), the intermediate wire becomes perfectly uniform. The set of mask pairs producing any specific intermediate value has cardinality exactly $q$ , independent of $G_1$ 's security parameter.
Positive Composition Theorem (Theorem 4.4): Demonstrates that a two-stage pipeline with fresh masking satisfies PF-PINI( $k_2$ ). The security of the composed output depends only on the second stage's parameter ( $k_2$ ); the first stage's weakness ( $k_1$ ) is completely erased.
Negative Composition Theorems (Theorems 5.1–5.3): Proves that without fresh masking, the intermediate wire retains the multiplicity of the first stage ( $k_1$ ). If $k_1 > 1$ , the wire is non-uniform, creating a necessary condition for DPA attacks.
Algebraic-Hardware Bridge (Theorem 6.1): Formally proves that the algebraic Barrett reduction map is equivalent to the hardware-faithful Nat arithmetic map under standard scope conditions ( $q \le 2^s$ ). This validates that the theoretical bounds apply directly to silicon implementations.
Adams Bridge Diagnosis: Formally instantiates the theorems to diagnose Microsoft's Adams Bridge accelerator. The proof confirms that the lack of fresh inter-stage masking leaves Barrett output wires non-uniform (PF-PINI(2)), explaining the success of prior empirical DPA attacks.
Universal 1-Bit Barrier: Provides computational evidence that the PF-PINI(2) bound is universal for modular reductions (both Barrett and Montgomery), suggesting a fundamental "1-Bit Barrier" for these operations.

4. Key Results

Formal Proof of Composition: The paper establishes that fresh inter-stage masking is the necessary and sufficient condition to compose arithmetic gadgets securely.
Quantitative Security:
- With Fresh Masking: The intermediate wire is uniform ( $k=1$ ). The final output is bounded by the second stage's parameter ( $k_2$ ).
- Without Fresh Masking: The intermediate wire is non-uniform (up to $k_1$ ). This non-uniformity is the root cause of the side-channel leakage observed in empirical attacks.
Adams Bridge Fix: The diagnosis confirms that adding a single fresh random mask register and a subtraction operation between the Butterfly and Barrett stages in the Adams Bridge pipeline would eliminate the DPA vulnerability on intermediate wires without changing the final output security parameter.
Artifact Availability: The full Lean 4 source code, including 18 theorems and a reproduction script, is publicly available, allowing independent verification of the proofs.

5. Significance

First Machine-Checked Arithmetic Composition: This is the first work to provide machine-checked composition theorems for arithmetic masking over prime fields, filling a major theoretical void in PQC hardware security.
Bridging Theory and Practice: By formally linking abstract algebraic proofs to hardware-faithful arithmetic, the paper provides a rigorous foundation for verifying real-world silicon designs, moving beyond empirical testing.
Design Guideline: It establishes a clear, provable design rule for PQC hardware: Always insert fresh masking between pipeline stages. This simple architectural change guarantees that the security of the composed pipeline is determined solely by the weakest link in the final stage, not the intermediate ones.
Convergence of Evidence: The formal proof aligns perfectly with three independent prior analyses (empirical power analysis, code review, and structural dependency analysis), confirming that the identified architectural flaw in the Adams Bridge accelerator is indeed the root cause of its vulnerability.

In summary, this paper provides the mathematical and formal verification backbone required to design secure, composable, and side-channel-resistant hardware accelerators for the new era of Post-Quantum Cryptography.