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

What it is

An ePrint preprint (2026/2578, received 21 October 2026, revised 24 October 2026) by MinGi Kim, YoungBeom Kim, DongHyun Shin and Seog Chung Seo. It gives a low-memory HAETAE implementation for Cortex-M4, Cortex-M3, MSP430 and AVR. HAETAE is a lattice signature scheme with shorter public keys and signatures than ML-DSA.

The baseline it improves on

• The HAETAE reference implementation needs a 158 KiB signing stack on Cortex-M4.
• Low-Stack HAETAE (CHES'26) cuts that to 5.7-5.9 KiB. HAETAE-2 still needs 8,718 B when the secret key and signature buffer share the same SRAM.
• Low-Stack regenerates Gaussian samples, which makes signing up to 2.6 times slower than the C reference.

How it works

• 16-bit storage. The modulus q = 64,513 fits in 16 bits, but signing and verification also need values modulo 2q, so existing code keeps 32-bit working polynomials. This work stores 16 bits and lifts each coefficient to modulo 2q in a register only when it is used.
• Shared buffers. Objects with disjoint lifetimes reuse the same memory. Together with 16-bit storage, this lowers peak stack without extra Gaussian regeneration.
• Exact Gaussian replay and caching. The first sampling pass records its acceptance decisions and partial CDT ranks in unused space in the signature buffer. The second pass restores the original samples from the same random stream with less recomputation.
• Arithmetic. NTT modular multiplication and butterflies are redesigned to keep 16-bit storage. The FFT and Gaussian sampler arithmetic are also optimized.

Results

• One C firmware image on an ATmega2560 (8 KiB SRAM) runs HAETAE-2 key generation, signing with the generated key, and verification. Total SRAM is 8,070 B, counting the secret key, signature buffer, static data and stack.
• The authors say this is the first standardization-track PQC signature implementation that signs within 8 KiB of total SRAM on physical hardware.
• Against Low-Stack HAETAE on all four targets, stack use falls by up to 34%. Key generation and signing run 1.18-2.51 times faster, wherever Low-Stack can run them.

Caveats

• It is a preprint with no peer-review venue listed.
• The speedup claim covers key generation and signing only. The page text gives no verification speedup and no per-platform cycle counts or per-parameter-set stack figures. The 8,070 B result is stated for HAETAE-2 only.
• The "first" claim is the authors' own, made "to the best of our knowledge".