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

Source: [Machine-Checked Cardinality Bounds for Masked Barrett Reduction: A 1-Bit Side-Channel Leakage Barrier in Post-Quantum Cryptographic Hardware](<https://www.sota2.com/research/paper/69f03f5d55a3c32af89fa3cd>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-04-30T05:00:12.461Z

Authors: Ray Iskander, Khaled Kirah

Published: 2026-04-27T16:27:33.000Z

## Abstract

Barrett reduction is the nonlinear core of every practical NTT-based post-quantum cryptography implementation. Existing composition frameworks (ISW, t-SNI, PINI, DOM) address Boolean masking over GF(2); none provides a machine-checked characterization of Barrett's leakage under first-order arithmetic masking and the first-order probing model over prime fields. Building on our prior series, QANARY \[15\], partial-NTT-masking margins \[14\], algebraic foundations \[16\], and butterfly composition \[18\], we close this gap. We prove a trichotomy: for any $q \> 0$ and shift $s$, the Barrett internal wire map $f\_x(m) = ((x + 2^s - m) \\bmod 2^s) \\bmod q$ has preimage cardinality in $\\{0, 1, 2\\}$, never more. We call this the 1-Bit Barrier: max-multiplicity 2 implies at most 1 bit of min-entropy loss per internal wire, universal over all moduli. The count-zero cases, unreachable output values, reveal that actual leakage is often strictly less than 1 bit, making the bound conservative. We introduce PF-PINI (Prime-Field PINI): Barrett satisfies PF-PINI(2); the Cooley-Tukey butterfly satisfies PF-PINI(1). We observe (not yet proved) that with fresh inter-stage masking, the composed pipeline has max-multiplicity $\\max(k\_1, k\_2)$, so the 1-Bit Barrier propagates. The trichotomy, the PF-PINI instantiations, and cardinality results are machine-checked in Lean 4 with Mathlib: 12 proved results, zero sorry, universal over all $q \> 0$ (the min-entropy bound follows by standard definitions). Adams Bridge lacks fresh inter-stage masking, violating PF-PINI composition and explaining why Papers 1 \[15\] and 2 \[14\] found vulnerabilities. NIST IR 8547 recommends formal methods for PQC implementation validation. The 1-Bit Barrier provides the first universal machine-checked cardinality bound for masked Barrett reduction in ML-KEM (FIPS 203) and ML-DSA (FIPS 204), with a corresponding 1-bit leakage interpretation.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Masking Verification on Barrett reduction over Zq](<https://www.sota2.com/research/sota/masking-verification-on-barrett-reduction-over-zq.md>): Masking Verification; Barrett reduction over Zq; Universal Score: 0.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2604.24670>)

[PDF](<https://arxiv.org/pdf/2604.24670.pdf>)
