Paper 2026/1422

LESS on the Cortex-M4: Characterizing the Speed–Memory Design Space of Code-Equivalence Signatures

Abstract

LESS is a code-based signature scheme built on the linear equivalence problem and, in its v2.0 round-2 form, a candidate in the NIST call for additional post-quantum signatures. No microcontroller implementation of it has been reported: the official benchmarking effort for the additional signatures excluded it on memory grounds, and an x86-massif cross-check puts the reference's peak stack at up to $\approx 836$~KB---beyond the SRAM of even the largest mainstream Cortex-M4. This paper provides the first such implementation, to the best of our knowledge---a complete characterization of LESS (v2.0) on the Arm Cortex-M4 across all seven parameter sets. NIST did not advance LESS to the third round in May 2026; we develop the implementation techniques and the evaluation methodology to outlast that outcome. We map the speed--memory design space with three operating points, all byte-identical to the NIST known-answer tests. The primary point is a \emph{balanced} configuration signing $4.1$--$4.3\times$ faster than the platform-normalized reference while using $41$--$59\%$ less peak stack. With double-pass signing at category~5, it is the only configuration whose signing we measured on target across all seven sets---at category~5, the resident-matrix configurations exceed the device's 640~KB of SRAM. It is flanked by a \emph{speed ceiling} at $4.5$--$4.7\times$ (at reference-level memory) and a \emph{memory floor} that signs with about a one-kilobyte measured stack at only $1.2$--$1.5\times$ reference time at category~1, with key generation on par with or below reference cost---so at category~1, memory minimization is nearly free. The speedups rest on three increasingly platform-specific layers: algorithmic restructuring, intrinsic-free two-lane SWAR (SIMD-within-a-register) arithmetic for $\mathbb{F}_{127}$ with a lazy-reduction scheme, and hand-scheduled assembly kernels---including a rank-2 row-elimination kernel---together with a systematic audit of all kernels against the Cortex-M4 timing rules. Read against the reference's own profile, these results indicate that implementation maturity, not the scheme, accounts for a $>4\times$ swing in achievable microcontroller signing---a data point for standardization-time performance evaluation, offered without revisiting the decision. We further report a catalog of negative results (techniques that help on desktop SIMD but hurt on the M4) and an alignment-safe transpose that returns $\approx 170$~KB of static memory to the stack under an \texttt{-O3} build. The evaluation methodology---Pareto-monotone adoption criteria, byte-identical correctness gates, and coverage and ablation reporting---transfers to the surviving third-round candidates, for which NIST has explicitly called for constrained-device evaluation.