Constant-Time Symmetry Exploitation for NTT Twiddle Factors in ML-KEM: A Unified Cost Model for Embedded Deployments
TL;DR
A Memory-Arithmetic Trade-off model is developed that unifies ROM, random-access memory (RAM), latency, energy, and side-channel risk into one device-aware objective and supports hardware-aware strategy selection with explicit assumptions on threat model and constant-time scope.
Abstract
: The standardization of the Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM, FIPS 203) creates urgent demand for efficient post-quantum cryptography on resource-constrained devices. In such deployments, twiddle-factor management in the Number Theoretic Transform (NTT) induces a practical trade-off: full tables reduce latency but consume read-only memory (ROM), while on-the-fly generation reduces ROM but increases arithmetic cost. This paper makes two contributions. First, we present a constant-time half-table strategy ( S hal f ) with branchless reconstruction logic and a formal indexing rule consistent with implementation. Second, we develop a Memory-Arithmetic Trade-off (MAT) model that unifies ROM, random-access memory (RAM), latency, energy, and side-channel risk into one device-aware objective. On ARM Cortex-M4, the proposed strategy reduces twiddle-factor ROM by 50% with a cycle overhead of about 3%–6% vs. full-table lookup in the same C framework. We additionally report cross-platform measurements on RISC-V and x86, where empirical best-strategy outcomes match MAT predictions. The resulting framework supports hardware-aware strategy selection with explicit assumptions on threat model and constant-time scope.