ICANEWS

Engineering & Technology

Machine-Checked Proofs Secure Pipelined Number Theoretic Transforms in PQC Hardware

Recent research, detailed in a paper titled Fresh Masking Makes NTT Pipelines Composable: Machine-Checked Proofs for Arithmetic Masking in PQC Hardware , presen

Machine-Checked Proofs Validate Arithmetic Masking for Pipelined PQC Hardware

Recent research, detailed in a paper titled Fresh Masking Makes NTT Pipelines Composable: Machine-Checked Proofs for Arithmetic Masking in PQC Hardware, presents significant advancements in ensuring the security of post-quantum cryptographic (PQC) accelerators. Specifically, the study focuses on the critical components of these accelerators: pipelined Number Theoretic Transform (NTT) stages over $\mathbb{Z}_q$. The work employs rigorous machine-checked proofs to validate the efficacy of arithmetic masking techniques, a fundamental approach for mitigating side-channel attacks.

The development of PQC accelerators is crucial for the implementation of cryptographic algorithms resilient to attacks from future quantum computers. Two prominent standards in this domain are ML-KEM (FIPS 203) and ML-DSA (FIPS 204), which heavily rely on pipelined NTT operations. Ensuring the security of these hardware implementations, particularly against sophisticated side-channel attacks, is paramount. This research addresses a long-standing gap in machine-checked formal verification for arithmetic masking in this context.

Addressing a Critical Security Verification Gap

Prior to this work, the assurance of pipeline-level security for per-stage arithmetic masking in NTT operations, especially for the r-bearing case, lacked machine-checked answers. Existing composition frameworks, such as ISW, t-SNI, PINI, and DOM, were exclusively formalized for Boolean masking over $\mathrm{GF}(2)$. This meant that the specific challenges of arithmetic masking over $\mathbb{Z}_q$, particularly within the NTT butterfly operation, had not been addressed by a proof assistant artifact.

The research directly tackles this limitation by providing robust, machine-checked proofs. This is a crucial step for the PQC community, as it offers a higher degree of assurance regarding the security properties of hardware implementations. The use of machine-checked proofs in Lean 4 with Mathlib, with all proofs being “zero sorry,” signifies a high level of formal rigor and correctness.

The Research Objective: Composability of Fresh Masking in NTT Pipelines

The core research question revolves around whether freshly applied per-stage arithmetic masking can guarantee pipeline-level security in NTT accelerators. Specifically, the study aimed to formally verify the security properties of these masked pipelines, particularly concerning the composition of masking techniques across multiple stages. The exact research topic, as stated in the source, is whether “per-stage arithmetic masking guarantees pipeline-level security” for “NTT Pipelines.”

Pipelined Number Theoretic Transform (NTT) stages are integral to the efficient execution of ML-KEM (FIPS 203) and ML-DSA (FIPS 204) algorithms. The security of these pipelines against side-channel attacks is dependent on robust masking schemes. The lack of machine-checked verification for arithmetic masking in these specific contexts presented a significant challenge, which this research sought to overcome. The explicit focus on the “r-bearing case” further highlights the specificity and depth of the investigation.

Key Findings from Machine-Checked Proofs

The researchers present three primary machine-checked results obtained using Lean 4 with Mathlib. These findings critically advance the understanding and verification of arithmetic masking in PQC hardware.

First Key Finding: Value-Independence and Marginal Distribution

The first significant finding addresses a stated limitation of prior work. The research demonstrates that value-independence implies constant marginal distribution when fresh randomness is used. This is achieved via an algebraic MutualInfoZero proxy. This result is crucial for understanding how the independence of masking values contributes to the overall security posture under fresh randomization. The concept of 'fresh randomness' is central to the efficacy of masking schemes, as it ensures that each operation receives statistically independent noise, thereby diversifying secret dependencies and frustrating side-channel attackers.

“First, we close a stated limitation of prior work: value-independence implies constant marginal distribution under fresh randomness (via an algebraic MutualInfoZero proxy).”

This finding has direct implications for cryptographic designers seeking to implement robust masking. By formally linking value-independence to constant marginal distribution, the research provides a foundational proof for a critical property of secure masking, ensuring that the distributions of intermediate values do not leak information about the secrets being processed.

Second Key Finding: Butterfly Per-Context Uniformity

The second machine-checked result concerns the NTT butterfly operation, a fundamental building block of the NTT. The study proves “butterfly per-context uniformity.” This means that for any Cooley-Tukey butterfly with a fresh output mask over $\mathbb{Z}/q\mathbb{Z}$ (where $q \neq 0$), each output wire has exactly one mask value that can produce each possible output. Furthermore, this uniform marginal distribution is independent of secrets and is universal across all moduli, twiddle factors, and inputs. This universality is a powerful claim, as it implies the security property holds under a wide range of operational parameters for the Cooley-Tukey butterfly.

“Second, butterfly per-context uniformity: for any Cooley-Tukey butterfly with fresh output mask over $\mathbb{Z}/q\mathbb{Z}$ ($q \neq 0$), each output wire has exactly one mask value producing each output, a uniform marginal independent of secrets, universal over all moduli, twiddle factors, and inputs.”

The uniform marginal distribution, being independent of secrets, is a hallmark of good masking. It means that an attacker observing the outputs of the butterfly operation cannot discern any information about the secret inputs, as all possible mask values lead to an equally likely distribution of observed outputs. This finding provides strong guarantees about the immediate security of individually masked butterfly operations, which are the atomic computational units in NTT pipelines.

Third Key Finding: K-Stage NTT Pipeline Security

The third and perhaps most encompassing finding extends the security guarantees to an entire pipeline. The research demonstrates that a k-stage NTT pipeline, when employing fresh per-stage masking, satisfies per-context uniformity at every stage. This proof is established under the ISW first-order probing model, a standard model for analyzing hardware security against side-channel attacks. This result is particularly significant because it addresses the composability of masking across multiple pipeline stages, which is often a complex challenge in hardware security.

“Third, a k-stage NTT pipeline with fresh per-stage masking satisfies per-context uniformity at every stage under the ISW first-order probing model.”

The satisfaction of per-context uniformity at every stage under the ISW first-order probing model provides strong evidence that the pipeline as a whole maintains its security properties. This implies that even if an attacker can probe individual wires at each stage, the fresh per-stage masking prevents them from extracting secret information due to the uniform marginal distribution introduced at each step. This finding is critical for ensuring the holistic security of PQC accelerators.

Methodology: Machine-Checked Proofs with Lean 4 and Mathlib

The rigorous nature of these findings stems directly from the methodology employed: machine-checked proofs. The proofs were developed and verified using Lean 4 with Mathlib, which is a formal proof assistant and its associated mathematics library. The fact that all proofs were “zero sorry” emphasizes that no assumptions were left unproven or unverified within the formal system, ensuring a high level of confidence in the correctness of the results. The artifact itself comprises nine theorems and required 1,738 build jobs for verification.

The choice of Lean 4 and Mathlib for formalization is significant. Proof assistants like Lean provide a framework for constructing mathematical proofs that are machine-verifiable. This eliminates human error and ambiguity often associated with traditional pen-and-paper proofs, offering the highest level of assurance for critical security properties. The explicit mention of “zero sorry” is a jargon indicating complete formal verification without any incomplete or placeholder proofs.

Specific Observations and Warnings

During the course of their research, the authors documented a specific warning: “pointwise value-independence is false for butterfly outputs.” This caution highlights a nuanced aspect of masking within the NTT butterfly operation, indicating that while the overall per-context uniformity holds, the pointwise independence of outputs might not be maintained, requiring careful consideration in design. This detail underscores the complexity involved in securing these computations.

Furthermore, the research provides a direct architectural critique related to existing hardware. The Adams Bridge accelerator, part of the CHIPS Alliance Caliptra project, is singled out. The study states that this accelerator “fails the fresh masking hypothesis” because its masking is “active only in INTT round 0.” This architectural choice “explain[s] its structural insecurity,” as it deviates from the requirement for fresh per-stage masking, which the study has shown to be crucial for pipeline-level security.

This explicit analysis of a real-world accelerator demonstrates the practical implications of the research. It provides concrete evidence for why certain masking strategies might lead to vulnerabilities and highlights the importance of adhering to principles like fresh per-stage masking. The failure to meet the “fresh masking hypothesis” directly negates the security guarantees established by the new proofs.

Implications for PQC Hardware Design

The findings have direct and significant implications for the design and implementation of PQC hardware accelerators supporting ML-KEM and ML-DSA. The machine-checked proofs provide a verifiable foundation for implementing secure NTT pipelines using arithmetic masking. Hardware architects can now rely on these formal guarantees when designing their PQC systems, moving beyond ad-hoc or unverified masking strategies.

The identified structural insecurity in the Adams Bridge accelerator serves as a critical case study, emphasizing that incomplete or non-fresh masking strategies can lead to demonstrable vulnerabilities. This underscores the need for thorough and formally verified masking throughout the entire pipeline, not just in select stages. The research strongly advocates for the adoption of fresh per-stage masking to achieve pipeline-level security.

Future Research Directions

The researchers also outline forthcoming work that will expand on the current findings. These future manuscripts will address the composition for nonlinear gadgets, specifically focusing on the Barrett modular reduction algorithm. One manuscript will prove Barrett's satisfaction of PF-PINI(2) (the 'one-bit barrier'), indicating its resistance to first-order side-channel attacks by demonstrating two shares are sufficient for security.

Another forthcoming manuscript will delve into k-stage composition for PF-PINI gadgets under fresh-mask renewal. This indicates a continued effort to extend the formal verification of masking techniques to more complex and iterative cryptographic operations commonly found in PQC hardware, further strengthening the security foundations of these critical systems.

This ongoing research trajectory emphasizes the commitment to providing comprehensive and formally verified solutions for mitigating side-channel risks in post-quantum cryptographic hardware, addressing highly specialized components like nonlinear gadgets which introduce their own unique masking challenges.

Key Findings