# Low-Stack HAETAE for Memory-Constrained Microcontrollers Source: [Low-Stack HAETAE for Memory-Constrained Microcontrollers]() Collection index: [llms.txt]() Data updated: 2026-04-21T05:00:04.784Z Authors: Gustavo Banegas, Kim Youngbeom, Seo Seog Chung, Vredendaal Christine Van Published: 2026-04-17T09:18:04.000Z ## Abstract We present a low-stack implementation of the module-lattice signature scheme HAETAE, targeting microcontrollers with 8 kB-16 kB of available SRAM. On such devices, peak stack usage is often the binding constraint, and HAETAE's hyperball-based sampler, large transient polynomial vectors, and variable-length signature payloads (hint and high-bits arrays) pose a particular challenge. To address this we introduce (i) Rejection-aware pass decomposition, which isolates encoding to the post-acceptance path; (ii) Component-level early rejection, which short-circuits the response computation when a partial norm already exceeds the bound; and (iii) Reverse-order streaming entropy coding using range Asymmetric Numeral Systems (rANS), which eliminates full hint and high-bits staging buffers. Combined with streamed matrix generation, a two-pass hyperball sampler with streaming Gaussian backend, and row-streamed verification, these techniques bring Signing stack from 71 kB-141 kB in the reference implementation down to 5.8 kB-6.0 kB, key generation to 4.7 kB-5.7 kB, and verification to 4.7 kB-4.8 kB across all three security levels. Our pure C implementation covers all three security levels (HAETAE-2/3/5), whose optimization paths differ due to the public-key domain (d\>0 vs. d=0) and rejection structure. We implement our optimization on a Nucleo-L4R5ZI and compare to the reference pqm4 (for HAETAE-2 and -3) and a recently published memory-optimized implementation (targeting HAETAE-5 only). We reduce HAETAE-2, -3, and -5 stack by respectively 75, 86 and 8 % for key generation, 92, 95 and 24 % for signature generation, and 85, 91 and 22 % for verification. Depending on the parameter set, this impacts performance by at most a factor 1.8 and 3.4 for key and signature generation respectively, while even offering a performance improvement up to 18 % for verification. Verification at all security levels fits within 8 kB of RAM (signature buffer + stack) and is 2.34-3.34x faster than ML-DSA m4fstack at each comparable security level. We additionally validate portability under RIOT-OS on ARM Cortex-M4 and RISC-V targets. ## Recorded benchmark results A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage. - [Digital Signature Signing on pqm4](): Digital Signature Signing; pqm4; Key Size (\|sk\|): 1. - [Digital Signature Verification on pqm4](): Digital Signature Verification; pqm4; Public Key Size: 1. - [Key generation on HAETAE-5](): Key generation; HAETAE-5; Cycles: 10423. - [Code size measurement on HAETAE 3](): Code size measurement; HAETAE-3; Text Segment Size: 38464. - [Verification on HAETAE-5](): Verification; HAETAE-5; Cycles: 2736. - [Verification on HAETAE-2](): Verification; HAETAE 2; Cycles: 1071. - [Verification on HAETAE 3](): Verification; HAETAE-3; Cycles: 2134. - [Signing on HAETAE-5](): Signing; HAETAE-5; Cycles (k): 163125. - [Code Size Measurement on HAETAE 2](): Code size measurement; HAETAE 2; Text Segment Size: 30416. - [Key generation on HAETAE 2](): Key generation; HAETAE 2; Cycles: 11518. - [Key generation on HAETAE-3](): Key generation; HAETAE-3; Cycles: 20998000. - [Signing on HAETAE 2](): Signing; HAETAE 2; Cycles: 81416. - [Signing on HAETAE 3](): Signing; HAETAE-3; Cycles: 138771. - [Code size measurement on HAETAE-5](): Code size measurement; HAETAE-5; Text Segment Size: 30150. - [Code size measurement on ML-DSA-44](): Code size measurement; ML-DSA-44; Text Segment Size: not recorded. - [Code size measurement on ML-DSA 65](): Code size measurement; ML-DSA-65; Text Segment Size: not recorded. - [Code size measurement on ML-DSA-87](): Code size measurement; ML-DSA-87; Text Segment Size: not recorded. - [Key generation on ML-DSA-44](): Key generation; ML-DSA-44; Cycles: not recorded. - [Key generation on ML-DSA-65](): Key generation; ML-DSA-65; Cycles: not recorded. - [Key generation on ML-DSA-87](): Key generation; ML-DSA-87; Cycles (k): not recorded. - [Signing on ML-DSA-44](): Signing; ML-DSA-44; Execution Cycles: not recorded. - [Signing on ML-DSA-65](): Signing; ML-DSA-65; Cycles: not recorded. - [Signing on ML-DSA-87](): Signing; ML-DSA-87; Cycles: not recorded. - [Verification on ML-DSA-44](): Verification; ML-DSA-44; Cycles: not recorded. - [Verification on ML-DSA-65](): Verification; ML-DSA-65; Cycles: not recorded. - [Verification on ML-DSA-87](): Verification; ML-DSA-87; Cycles: not recorded. ## Original sources and implementation [Original paper]() [PDF]()