1970-01-01

(2026-08) Code Generation of Faster Formally Verified NTT with Plantard Reduction

Donnie Y. Xu
Rajeev Gore
Amin Sakzad
Ron Steinfeld
Raymond K. Zhao

2026-08-06

Abstract

We present a formally verified implementation of the ML-KEM Number-Theoretic Transform (NTT) based on Plantard arithmetic, produced via a code generator that targets ML-KEM, ML-DSA, and FN-DSA from a single parameter triple. The generator embeds a static bound analyzer that places modular reductions at code-generation time without runtime branching, eliminating per-scheme manual tuning while preserving constant-time guarantees. Each generation produces structurally identical implementations in two backends: portable C, and Jasmin for formal verification. To establish end-to-end correctness, we contribute a parametric formalization of Plantard arithmetic in \textsc{EasyCrypt} and a layer-by-layer program-equivalence proof connecting the extracted Jasmin ML-KEM NTT to the abstract specification of formosa-mlkem; the existing algebraic chain is reused unchanged to extend correctness down to the mathematical NTT definition. Benchmarks across three schemes show that the generated code outperforms reference C by $1.5\times$ -- $1.8\times$ on the forward NTT and $1.7\times$ -- $2.5\times$ on the inverse, and outperforms the formally verified formosa-mlkem Jasmin baseline by $1.26\times$ and $2.19\times$ on ML-KEM. We believe our techniques generalize to other lattice-arithmetic primitives requiring both performance and formal verification.