Paper 2026/2578

HAETAE on a Diet: Less Stack, Less Time on Low-End Microcontrollers

Abstract

HAETAE has shorter public keys and signatures than ML-DSA, but the signing stack of its reference implementation reaches $158\, \mathrm{KiB}$ on Cortex-M4. The Low-Stack HAETAE implementation presented at CHES'26 brings the signing stack down to $5.7$-$5.9\,\mathrm{KiB}$; yet even HAETAE-2 still needs $8,718\,\mathrm{B}$ in a realistic IoT scenario, where the secret key and the signature buffer share the same SRAM. Gaussian regeneration further increases signing time by up to a factor 2.6 relative to the C reference. Although HAETAE's modulus $q = 64\,513$ fits in 16 bits, signing and verification also need values modulo $2q$, so existing implementations keep 32-bit working polynomials. We store them in 16 bits and lift each coefficient to modulo $2q$ in a register only when it is consumed, and let objects with disjoint lifetimes share buffers, which lowers peak stack usage without any additional Gaussian regeneration. Exact Gaussian replay and caching method then record the acceptance decisions and partial CDT ranks of the first generation in the unused space of the signature buffer, so that the original samples are restored from the same random stream with less recomputation. For Cortex-M4, Cortex-M3, MSP430, and AVR, we further design NTT modular multiplication and butterflies that preserve 16-bit storage, and optimize the arithmetic of the FFT and the Gaussian sampler. We validate our implementation on $8\,\mathrm{KiB}$ hardware: a single C firmware image on the ATmega2560 runs HAETAE-2 key generation, signing with the generated key, and verification, and uses a total of $8,070\,\mathrm{B}$ of SRAM, including the secret key, the signature buffer, static data, and the stack. To the best of our knowledge, this is the first standardization-track PQC-DSA implementation that signs within $8\,\mathrm{KiB}$ of total SRAM on physical hardware. Compared with Low-Stack HAETAE on Cortex-M4, Cortex-M3, MSP430, and AVR, our implementation reduces stack usage by up to 34% and runs key generation and signing 1.18-2.51$\times$ faster wherever Low-Stack can run them.