← All papers
First page of Prime-Field PINI: Machine-Checked Composition Theorems for Post-Quantum NTT Masking

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

Ray Iskander, Khaled Kirah

cs.CR Apr 28, 2026 · v1
Formalizes prime-field masking composition theorems in Lean 4 (18 proofs, zero sorry).
This is Paper 6 of a series of formally-verified analyses of masked NTT hardware for post-quantum cryptography; Paper 1 [1] established structural dependency analysis of the QANARY platform, and Paper 2 [2] quantified security margins under partial NTT masking. Boolean masking composition is well-understood through NI, SNI, and PINI. Arithmetic masking over $\mathbb{Z}_q$ for prime $q$, the foundation of NTT-based post-quantum cryptography, has lacked an analogous theory. We prove, to our knowledge, the first machine-checked composition theorems for arithmetic masking over prime fields. Our key insight is the renewal argument: when a fresh random mask is applied between two pipeline stages, the intermediate wire becomes perfectly uniform regardless of Stage 1's security parameter. For two PF-PINI gadgets with parameters $k_1$ and $k_2$, the composed two-stage pipeline with fresh masking satisfies PF-PINI($k_2$), Stage 1's multiplicity is completely erased from the composed output. Without fresh masking, intermediate wires have multiplicity up to $k_1$, creating a necessary condition for differential power analysis. We formalize both theorems in Lean 4 with 18 machine-checked proofs and zero sorry stubs. We formally bridge the algebraic and hardware-faithful arithmetic models of Barrett reduction, and instantiate the theorems to formally diagnose Microsoft's Adams Bridge PQC accelerator: its absence of fresh inter-stage masking leaves Barrett output wires non-uniform under the first-order probing model, the same architectural flaw that two independent empirical analyses [3, 4] and our own prior structural analysis [1] identified. Computational evidence further suggests the 1-Bit Barrier is universal across Barrett and Montgomery reductions.

Arithmetic masking over prime fields Z_q, which underpins NTT-based post-quantum cryptography, lacked machine-checked composition theorems analogous to those available for Boolean masking (NI, SNI, PINI).

The authors prove machine-checked composition theorems for arithmetic masking over prime fields. Their key insight is a renewal argument: when a fresh random mask is applied between two pipeline stages, the intermediate wire becomes perfectly uniform regardless of the first stage's security parameter. The proofs are formalized in Lean as part of a series on masked NTT hardware verification.

For two PF-PINI gadgets with parameters k_1 and k_2, the composed two-stage pipeline with fresh masking satisfies PF-PINI(k_2), completely erasing Stage 1's multiplicity from the composed output. This is reported as the first machine-checked composition theorem for arithmetic masking over prime fields.