Low-Stack HAETAE for Memory-Constrained Microcontrollers Gustavo Banegas1 , YoungBeom Kim2 , Seog Chung Seo2 and Christine van Vredendaal3 LIX, CNRS, Inria, École Polytechnique, Institut Polytechnique de Paris, France [email protected] 2 Kookmin University, Seoul, Republic of Korea, {darania,scseo}@kookmin.ac.kr 3 NXP Semiconductors, The Netherlands, [email protected]
arXiv:2604.15868v1 [cs.CR] 17 Apr 2026
1
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.34× 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. Keywords: HAETAE · lattice-based cryptography · small memory signatures · constrained devices
1
Introduction
Embedded systems rely on public-key authentication schemes for firmware updates, secure boot, device attestation, and device provisioning. With the transition to post-quantum ∗ Author list in alphabetical order; see https://ams.org/profession/leaders/CultureStatement04. pdf. This work was supported by the HYPERFORM consortium, funded by France through Bpifrance, and by the France 2030 program under grant agreement ANR-22-PETQ-0008 PQ-TLS. Date of this document: 2026-04-20.
2
Low-Stack HAETAE for Memory-Constrained Microcontrollers
cryptography, signature schemes based on module lattices are leading candidates for standardization. On low-end ARM Cortex-M and RISC-V microcontrollers, the stack available to an application may be only 8 kB–16 kB once the real-time operating system (RTOS), network stack, and I/O drivers are loaded. For this class of targets, peak stack usage is often the binding constraint rather than code size or cycle count. HAETAE [CCD+ 23, CCD+ 24], a module-lattice signature scheme presented at CHES’24, achieves shorter signatures and keys than ML-DSA [NIS23] by sampling ephemeral vectors from a hyperball rather than a hypercube. This compactness reduces communication and persistent storage costs, making HAETAE attractive for constrained deployments. For its attractive qualities, it has been identified as a winner in the Korean domestic post-quantum cryptography competition, KpqC [Kor]. Motivation. Although HAETAE offers smaller public keys and signatures than ML-DSA at comparable security levels (Table 1), the reference implementation requires 71 kB to 141 kB of peak stack during the signing operation, depending on the security level, far exceeding the RAM budget of typical embedded targets. The root cause is that multiple large polynomial vectors used in sampling, challenge derivation, and hint computation are kept live simultaneously. The hyperball sampler amplifies the problem: because the scaling factor depends on the squared norm of the full Gaussian sample, a one-pass implementation must buffer the entire sample before producing any output. This issue extends beyond signing. In modern embedded systems, key generation may also be performed at runtime for ephemeral credentials or key rotation, and verification must complete within tight stack budgets on sensor nodes that only verify signatures. A practical low-memory implementation should therefore address key generation, signing, and verification alike. Related work. Bos, Renes, and Sprenkels [BRS22] showed that ML-DSA can fit within a few kilobytes of stack by trading recomputation for peak memory, streaming seedderived objects, and reusing lifetime-disjoint buffers; similar strategies have been applied to FrodoKEM [BBC+ 23]. For HAETAE, however, only streaming matrix generation and sparse challenge multiplication carry over directly; the hyperball sampler, variablelength rANS encoding, and hint computation remain unaddressed by [BRS22]. To the best of our knowledge, [HCK+ 26] is the state-of-the-art memory-optimized HAETAE implementation on Cortex-M4. Following [BRS22], it achieves 5,212 B/8,092 B/6,220 B (key generation/signing/verification) for HAETAE-5, approaching the idealized baselines of Section 3. However, it targets HAETAE-5 only, leaving HAETAE-2/3 (d>0, different public-key domain and rejection structure) unaddressed, and its verification stack (6,220 B) plus the signature (2,948 B) totals 9,168 B, exceeding the 8 kB budget of many constrained devices. Fitting within this budget requires optimizations beyond general streaming, targeting HAETAE-specific components that prior work leaves unexplored.
1.1
Contributions
Support for all HAETAE security levels. We address both gaps identified above: our implementation supports all three security levels (HAETAE-2/3/5), with separate optimization paths for the d>0 (HAETAE-2/3) and d=0 (HAETAE-5) cases (Section 4.1), and fits verification within the 8 kB budget at every level. Our pure C implementation achieves 4.7 kB–5.7 kB key generation stack, 5.8 kB–6.0 kB signing stack, and 4.7 kB–4.8 kB verification stack across all levels, with .data = 0 and .bss = 0.
Gustavo Banegas, YoungBeom Kim, Seog Chung Seo and Christine van Vredendaal
3
Novel stack optimization techniques. We introduce optimization techniques tailored to HAETAE’s algorithmic structure that push the measured stack below the idealized streaming baselines (Section 3). For signing (Section 4.2), we introduce (i) Rejectionaware pass decomposition, which confines large buffers to non-overlapping lifetime phases; (ii) Component-level early rejection, which short-circuits the response computation when a partial norm exceeds the bound; and (iii) Reverse-order streaming entropy coding, which eliminates full hint and high-bits staging arrays. The signing path additionally employs a streaming two-pass hyperball sampler with a fully streaming Gaussian backend (.bss = 0), for which we provide a formal correctness proof (Section 4.4). For verification (Section 4.3), we combine row-streamed matrix multiplication with view-style decoding, replacing a large vector accumulator with a single polynomial and a compact union overlay. For HAETAE-5, these yield 4,816 B key generation (−7.6 % vs. [HCK+ 26]), 6,136 B signing (−24 %), and 4,840 B verification (−22 %), while key generation, signing, and verification are 25 %, 27 %, and 16 % faster respectively. Evaluation and practical applicability. We evaluate on the pqm4 framework and additionally validate portability under RIOT-OS on Cortex-M4 (nRF52840) and RISC-V (ESP32-C6) targets. On 8 kB devices, verification at all HAETAE security levels fits within budget (signature buffer + stack), and is 2.34–3.34× faster than ML-DSA m4fstack [BRS22] at each comparable security level. On 16 kB devices, all HAETAE levels support full signing (secret key + signature + stack), whereas ML-DSA-87 exceeds this budget. Constant-time implementation. Our implementation avoids branches and memory accesses that depend on long-term secret coefficients, with the exception of the rejectionsampling loop inherent in the Fiat-Shamir-with-Aborts paradigm; verification processes only public inputs. Countermeasures against power analysis or fault attacks are not addressed in this work. Our implementation will be available upon acceptance of the paper.
2
Background
In this section, we briefly explain the mathematical and algorithmic background of HAETAE, covering its algebraic setting, parameter sets, and core operations. Implementationoriented algorithm specifications based on the latest HAETAE specification [Kpq26] are provided in Appendix A–C.
2.1
HAETAE
HAETAE is a module-lattice signature scheme operating in the polynomial ring Rq = Zq [X]/(X N + 1), with q a prime modulus. Vectors of ℓ (resp. k) polynomials are called polyvecl (resp. polyveck) and occupy ℓ · N · 4 (resp. k · N · 4) bytes when stored with 32-bit coefficients. Polynomial multiplication in Rq is performed efficiently via the Number Theoretic Transform (NTT), which maps a polynomial to its evaluation at the 2N -th roots of unity modulo q and reduces multiplication to a pointwise product in O(N log N ) time. Parameter sets. HAETAE is specified at three security levels. Table 1 lists the parameters referenced in this paper. All three sets share the polynomial degree N =256 and modulus q=64,513. The module dimensions (k, ℓ) determine the sizes of the public matrix A ∈ Rqk×ℓ and the secret/response vectors, and are the primary driver of memory usage. The
4
Low-Stack HAETAE for Memory-Constrained Microcontrollers Table 1: Selected HAETAE parameters. |poly| = N × 4 = 1,024 B. Parameter
Description
HAETAE-2
HAETAE-3
HAETAE-5
N q (k, ℓ) τ d α αh
polynomial degree modulus module dimensions challenge weight PK truncation z1 compression h compression
256 64 513 (2, 4) 58 1 256 512
256 64 513 (3, 6) 80 1 256 512
256 64 513 (4, 7) 128 0 256 256
|pk| |sk| |sig|
public key (bytes) secret key (bytes) signature (bytes)
992 1 408 1 474
1 472 2 112 2 349
2 080 2 752 2 948
truncation parameter d governs the public-key format: d=1 (HAETAE-2/3) stores a rounded representation, while d=0 (HAETAE-5) stores the NTT-domain image directly (Section 2.1). Like ML-DSA [NIS23], HAETAE is constructed in the Fiat–Shamir with Aborts (FSwA) framework [Lyu09]. In FSwA, the signer commits to an ephemeral randomness y, receives (or derives) a binary challenge c of low Hamming weight, and computes a masked response z = y + (−1)b (c ⋆ s). An abort (rejection) step is performed to ensure that the distribution of z does not leak information about the secret s. The key distinction between ML-DSA and HAETAE lies in the distribution from which the ephemeral y is drawn, as detailed in Section 2.2. HAETAE makes extensive use of HighBits and LowBits decompositions; we abbreviate these as HB and LB throughout, with superscripts (h, z1 , pk) indicating the decomposition type. For HAETAE-2/3 (d=1), the verification key stores only the high-order bits b1 = HBpk (b) together with a public seedA for expanding the matrix. The low-order bits b0 = LBpk (b) are folded into the secret key. For HAETAE-5 (d=0), no rounding is applied; b = NTT(−2b) is stored directly in the NTT domain. instead b The signature and key sizes of HAETAE are smaller than those of ML-DSA at comparable security levels, owing to the hyperball-based sampling strategy described below. At HAETAE-2 (targeting NIST security level 2), the signature size is 1 474 bytes, making it competitive with other lattice-based signatures while remaining efficient to verify. Key Generation. Key generation expands a seed into the public matrix A ∈ Rqk×ℓ and secret vectors (s1 , s2 ), then computes b = As1 + s2 mod q. Unlike ML-DSA, HAETAE applies an explicit singular-value norm check N (s1 , s2 ) ≤ γ 2 N that rejects and resamples until the bound is satisfied; this rejection loop and its FFT-based workspace affect the key-generation stack peak. The implementation differs across security levels: for HAETAE2/3 (d>0), b is rounded and the public key stores b1 = HBpk (b), while for HAETAE-5 b = NTT(−2b) is stored directly in the NTT domain. The norm rejection also (d=0), b differs: HAETAE-2/3 interleave it with the matrix–vector multiplication, while HAETAE-5 performs it before expanding A. See Algorithm 3 and 4 in Appendix A for the detailed specifications. Signing. Unlike ML-DSA, which samples y uniformly from a hypercube, HAETAE draws y = (y1 , y2 ) from a discretized hyperball: coefficients are sampled from a discrete Gaussian Dσ , the vector is rescaled so that ∥(y1 , y2 )∥2 ≤ B0 Λ, and a norm rejection test is applied. This yields shorter signatures but requires a more expensive and memory-intensive sampler (Section 4.4). In the signature operation, the signer derives µ = H(pk, M ) and repeats the steps of sampling y, computing w = A⌊y1 ⌉ mod 2q, deriving challenge c, and forming z = y +
Gustavo Banegas, YoungBeom Kim, Seog Chung Seo and Christine van Vredendaal
5
Figure 1: Overview of RIOT-OS modularization packages. (−1)b c⋆s. If z passes the norm bounds, the hint h = HBh (w′ )−HBh (w′ −2⌊z2 ⌉) is computed and the signature σ = (HBz1 (⌊z1 ⌉), LBz1 (⌊z1 ⌉), h, c) is encoded. See Algorithm 5 in Appendix B. A naïve implementation keeps y, w, z, and encoding buffers live simultaneously, totaling (ℓ+2k) · |poly| of ring objects (e.g. over 12 kB for HAETAE-5). The hyperball sampler amplifies this: the scaling factor depends on the norm of the full Gaussian sample, so a one-pass implementation must store all (L+K) · N coefficients before producing any output. Verification. Verification (Algorithm 6 in Appendix C) parses the signature, reconstructs w̃ = Az̃1 mod 2q, recomputes the challenge from h̃ + HBh (w̃′ ) and the message digest, and accepts if the recomputed challenge matches and all norm bounds hold. There is no rejection loop or secret-dependent sampler, but materializing the matrix product, decoded signature, and hint buffers simultaneously can still require substantial stack space.
2.2
Applicable ML-DSA Memory Optimization
Due to the similarity of the schemes, the memory-optimization techniques of [BRS22] can be applied to the operations common between HAETAE and ML-DSA. Both schemes are module-lattice Fiat–Shamir signatures with the same high-level shape: seed expansion to generate a public matrix A; computation of a public commitment involving A and short secret vectors; a sign-then-reject loop in which an ephemeral sample is masked by a low-weight challenge; and verification by recomputing the challenge from the response and the public key. Both also rely on NTT-based polynomial arithmetic and HB/LB decompositions to compress intermediate values. This structural similarity means that the streaming and liveness-reduction ideas from [BRS22] carry over to HAETAE with appropriate adaptation. The primary algorithmic difference is the distribution from which the ephemeral randomness y = (y1 , y2 ) is drawn. ML-DSA samples y uniformly from a hypercube: each coefficient is drawn independently and uniformly from {−γ1 + 1, . . . , γ1 }. HAETAE instead samples y from a discrete Gaussian conditioned on a hyperball: coefficients are drawn from a discrete Gaussian, the vector is rescaled so that its Euclidean norm lies in [ 0, B0 Λ ], and a Euclidean norm rejection test is applied. This hyperball sampling yields shorter signatures and keys because it more efficiently fills the acceptance region, but at the price of a more expensive and memory-intensive sampler (see Section 4.4). In ML-DSA, the public key is (ρ, t1 ), where t1 is the high-order part of As1 + s2 . The matrix seed ρ is stored explicitly, and the secret key additionally holds t0 (the low-order residue) to enable efficient signing. In HAETAE, the public key is (seedA , b1 ), where b1 is the high-order part of a related lattice commitment b. The HAETAE secret key is more compact; it stores a single short vector s of augmented dimension k + ℓ + 1 and a nonce K—because the lattice relation allows the signer to recover the full signing basis on-the-fly.
6
Low-Stack HAETAE for Memory-Constrained Microcontrollers
Algorithm 1 Schematic HAETAE (Key generation, Signing, Verification) 1: procedure Key Generation(1λ ) 2: Sample seeds ρ, κ; sample (s1 , s2 ) 3: Reject if N (s1 , s2 ) > γ 2 N ▷ FFT-based singular-value norm 4: Expand ρ 7→ A; compute b ← As1 + s2 mod q; output (pk, sk) 5: end procedure 6: procedure Signing(sk, M ) 7: Derive µ ← H(pk, M ) 8: repeat 9: Sample (y1 , y2 ); compute w ← A⌊y1 ⌉ mod 2q 10: c ← SampleBinaryChallengeτ (H(HBh (w′ ), LSB(⌊y1,1 ⌉), µ)) 11: z ← y + (−1)b c ⋆ s 12: until z passes rejection tests 13: h ← HBh (w′ ) − HBh (w′ − 2⌊z2 ⌉) ▷ post-acceptance 14: σ ← (HBz1 (⌊z1 ⌉), LBz1 (⌊z1 ⌉), h, c) 15: end procedure 16: procedure Verification(pk, M, σ) 17: Parse σ into (HBz1 , LBz1 , h, c); reconstruct z̃1 18: w̃ ← Az̃1 mod 2q; recompute c′ from (h̃ + HBh (w̃′ ), µ) 19: Accept iff c′ =c and norm bounds hold 20: end procedure
2.3
RIOT-OS
RIOT [RIO] is an open-source operating system targeting resource-constrained IoT devices. Originally introduced in [BHG+ 13], it is written in C and designed with portability in mind, which allows it to support a broad range of boards and architectures. Figure 1 shows the modular structure of RIOT. The most left part in the figure corresponds to hardware-independent components, whereas the right part contains hardware-specific ones. This design enables RIOT to reuse most of its code across platforms and to favor portable C implementations instead of relying on architecture-specific intrinsics or assembly code.
3
Idealized memory baselines for HAETAE
Before describing the concrete implementation techniques in Section 4, we analyze the idealized memory footprint of each HAETAE routine by counting only the dominant ring objects (polynomials and polynomial vectors) while ignoring constant-size overheads such as hash states, scalar variables, and call frames. This analysis clarifies the relationship between the number of simultaneously live large ring objects and the achievable peak stack. Dominant objects. All three HAETAE parameter sets use N =256; a single polynomial with 32-bit coefficients occupies |poly| = 1 024 B. The public matrix A ∈ Rqk×ℓ has k rows and ℓ columns; a polyveck (k polynomials) and polyvecl (ℓ polynomials) scale linearly. For HAETAE-5 (k=4, ℓ=7) these are 4 096 B and 7 168 B respectively. High-level algorithms. We summarize the HAETAE workflow in Algorithm 1; it is intentionally schematic since our implementation keeps the mathematics unchanged while reorganizing the order in which objects are materialized. We use the HB/LB abbreviations introduced in Section 2.1. Key generation. The reference implementation materializes A, s1 , and b simultaneously (≈ (kℓ+ℓ+k) · |poly|). Since both A and s1 are deterministically expandable from seeds, the matrix–vector product can be streamed with 2·|poly| (one row accumulator plus one sampling scratch). However, the singular-value norm check N (s1 , s2 ) ≤ γ 2 N requires an
Gustavo Banegas, YoungBeom Kim, Seog Chung Seo and Christine van Vredendaal
7
Table 2: Streaming baselines vs. measured stack on pqm4 (HAETAE-5, bytes). Baselines count dominant ring objects and staging buffers; constant-size overheads (hash states, scalars, call frames) are excluded. Full performance results are in Table 3. Key generation Signing Verification
Idealized baseline
[HCK+ 26]
Ours
2 × 1 024 + 2 048 = 4 096 (k+3) × 1 024 + ℓ·N = 8 960 (k+2) × 1 024 = 6 144
5 212 8 092 6 220
4 816 6 136 4 840
FFT-based computation with a 2 048 B workspace, giving a total baseline of 2·|poly| + 2 048 = 4 096 B. Signature generation. The reference implementation keeps y1 (ℓ polys), y2 and w (2k polys), and the hint h live simultaneously, totaling ≈ (ℓ+2k) · |poly| (e.g. 12 288 B for HAETAE-5). With standard streaming, y and w can be regenerated row by row from seeds, but the full hint buffer h ∈ Rk , the high-bits array HBz1 (z1 ) ∈ Zℓ×N , and the challenge polynomial c must still be materialized before the rANS encoder can process them. In particular, c remains live throughout the rejection test and the packing phase, coexisting with the hint and streaming buffers. This gives a streaming baseline of (k+3) · |poly| + ℓ·N bytes (e.g. 7 168 + 1 792 = 8 960 B for HAETAE-5). b ◦ Verification. A column-streamed approach accumulates the matrix product w̃ = A NTT(z̃1 ) into a full polyveck buffer while sweeping z̃1 once. The challenge polynomial c must also remain live for the final comparison, giving a baseline of (k+2) · |poly| (e.g. 6 144 B for HAETAE-5). Summary and outlook. Table 2 summarizes the baseline streaming footprints for HAETAE-5; these baselines count dominant ring objects and staging buffers while excluding seeds, hash states, and other implementation-specific overheads. The same analysis applies to HAETAE-2/3 with adjusted (k, ℓ) values, though differences in the public-key domain (d>0 requires an additional rounding step and a-vector) and the placement of the rejection loop affect the concrete figures. The prior work of [HCK+ 26] reports HAETAE-5 stack usage close to these baselines: 5,212 B (Key generation), 8,092 B (Signing), and 6,220 B (Verification). In the next section we introduce additional techniques, including pass decomposition with noinline boundaries, reverse-order streaming entropy coding, and row-streamed verification, that push the stack footprint below these idealized baselines. Section 5.2 confirms that the resulting implementation achieves lower stack usage while retaining competitive cycle counts relative to [HCK+ 26].
4
Low-footprint memory techniques
In this section, we describe the main techniques we use to reduce the memory footprint of HAETAE key generation, signing, and verification. Our approach is guided by the principle of trading increased computation time for reduced peak stack footprint, which is essential for predictable execution on memory-constrained microcontrollers. We also leverage the structure of HAETAE’s algorithms, such as the use of seed-derived objects and sparse challenges, to enable streaming and in-place computation strategies that minimize stack usage.
8
Low-Stack HAETAE for Memory-Constrained Microcontrollers
128
|←−−→| ρ, σ, K
1024
|←−−−→|
1024
|←−−−→|
1024
|←−−−→| sum=0
s1,j
b (b + s2,i ) b (b + ai ) b0
ŝ1,j
s2,i
s2 N (sum)
check
ρ, σ, K := (seedA , seedsk , K) ← Hgen (seed) sum ← 0 2 s1,j ← ExpandS(σ, j (col)) 2 3 write s1,j to sk; sum += ∥s1,j ∥ (where i=0) 4 ŝ1,j ← NTT(s1,j ) 5 b̂ := b̂ + Âi,j ◦ ŝ1,j (streamed Âi,j ) −1 6 b := NTT (b̂) 7 s2,i := ExpandS(σ, i (row)) 8 b ← b + s2,i 9 b ← b + ai (streamed ai ) pk pk 10 b0 := LB (b); write HB (b) to pk 11 s2 := s2,i − b0 2 12 write s2 to sk; sum += ∥s2 ∥ 2 13 reject if N (sum) > γ N 14 pack_remain_pk(ρ), pack_remain_sk(K) 0
1
0≤i<k
b̂ = 0 b̂ b
reject 0≤j<ℓ
Figure 2: Memory allocation of the proposed memory-optimized HAETAE-2,3 key generation with streaming. This approach streams the matrix  on-the-fly and reuses memory slots, keeping only two single polynomials (poly b, s) and one norm accumulator (int32_t sum[N]) on the stack. The dashed arrow indicates the rejection loop unique to HAETAE-2,3.
4.1
Low-stack key generation via streaming
When key generation for digital signatures on constrained devices is required to be performed at runtime, it can no longer be circumvented with a one-time provisioning step. Practical applications include generating ephemeral keys for firmware integrity verification and implementing key rotation to mitigate compromise. The baseline key generation is specified in Algorithms 3 and 4 (Appendix A). We describe our stack optimizations in two parts. First we present the streaming techniques applied to HAETAE-2/3 (d > 0), which involve rounding and an additional a-vector not present in the d=0 case; this streaming of key generation for d > 0 is a new contribution not covered in previous work. Figure 2 illustrates the resulting memory layout. We then describe our HAETAE-5 (d = 0) implementation, which follows the same high-level approach as [HCK+ 26], but further compresses the stack through caller-level union analysis. Streaming matrix–vector multiplication. Key generation computes b = a + As1 + s2 (mod q), where A ∈ Rqk×ℓ is derived from a seed and s1 ∈ Rqℓ , s2 ∈ Rqk are short secret vectors. The reference implementation materializes A and b s1 as full polynomial vectors, causing large stack pressure. We reorganize the computation so that s1 , s2 , and A are all generated and consumed on-the-fly (steps 2 – 12 in Figure 2): for each column j we sample s1,j into a single scratch polynomial ( 2 ), apply the NTT in place ( 4 ), and for each row i generate Ai,j from the seed and immediately accumulate the pointwise product into bi ( 5 ). The secret vectors are written to the secret key as they are produced ( 3 , 12 ), and a norm accumulator (int32_t sum[N]) tracks the singular-value check incrementally ( 13 ); s1 norms are accumulated only at i=0 to avoid redundant computation in the inner loop. The entire key generation thus requires only two single-polynomial scratch slots (poly b, s) and one norm accumulator on the stack. Additional stack reductions. SHAKE-based sampling routines (poly_uniform, and poly_uniform_eta) are rewritten to squeeze one block at a time, replacing multi-block stack buffers with a single-block buffer without altering the output distribution. Together with the streaming matrix multiplication and the fused frozen-A variant, these techniques remove full-vector temporaries, stack-local expansion buffers, and multi-block squeeze buffers, yielding a substantially smaller and more predictable stack profile. Note that
Gustavo Banegas, YoungBeom Kim, Seog Chung Seo and Christine van Vredendaal
160
|←−−→| seeds, µ
1024
|←−−−→|
1024
|←−−−→|
9
1024
|←−−−→| 0 reject
derive µ, seedybb ; κ ← 0
— Pass A: row-streaming w and challenge —
ŵi =0
0≤j<L
ytmp [ ytmp
1 2
0≤i<K
wi wi′
ytmp ← ExpandYbb(seedybb , κ)j b i,j ◦ NTT(ytmp) ŵi += A
b ▷ streamed A
wi ← NTT−1 (ŵi ) + 2 · ⌊y2,i ⌉ mod q wi′ ← fromCRT(wi , ⌊y1,1 ⌉) h ′ ′ 5 w1,i ← HB (wi ) ′ 6 absorb w1,i into H 3 4
▷ incremental transcript hashing ′ 7 ρ ← H(w1 , LSB(⌊y1,1 ⌉), µ)
c
8
yi
b si
c ← SampleBinaryChallengeτ (ρ)
— Pass B: streaming rejection check — 0≤i<L+K −1 b 9 zi ← yi + (−1) NTT (b c◦b si ) ▷ fused; early reject if ∥z1,0 ∥2 > B12 2 2 10 ∥z∥ += ∥zi ∥ ; discard zi
zi
′ 11 (early) reject if ∥(z1 , z2 )∥2 ≥ B ; repeat Pass A, B
wi
z2,i
K−1≥i≥0
— Pass C: post-acceptance (noinline) — h ′ ′ 12 C1 : hi ← w1,i − HB (wi − 2⌊z2,i ⌉)
⌊z1,i ⌉
b s1,i
L−1≥i≥0
▷ hi,j streamed to rANS encoder (no h buffer); i=K−1↓0 z z 13 C2 : σ ← PackSig(HB 1 (⌊z1,i ⌉), LB 1 (⌊z1,i ⌉)) ▷ HB(z1,i,j ) streamed to rANS encoder (no HB buffer); i=L−1↓0 z 14 HB 1 copy-out at end of C2 ; h appended at finalization
Figure 3: Memory allocation of the proposed pass-decomposed HAETAE signing. The driver holds persistent state (seeds, µ; 160 B) and a single 1 024 B polynomial slot that serves as the row accumulator ŵi for the matrix–vector product in Pass A and holds the challenge c from Pass B onward. Two additional poly-sized scratch slots (1 024 B each) are reused across passes. The dashed arrow marks the rejection loop (Pass A + B only); Pass C runs once after acceptance. C1 and C2 are invoked via noinline, so their frames never coexist. Reverse-order loops (i↓, j↓) in C1 /C2 stream coefficients directly to the rANS encoder, eliminating full h and HB(z1 ) staging buffers.
streaming and re-computation alter data-access patterns; a thorough side-channel analysis is left for future work.
HAETAE-5 (d = 0) key generation. For HAETAE-5, the key generation follows the same high-level streaming approach as prior work [HCK+ 26]: on-the-fly matrix generation, b = NTT(−2b), and direct storage in the NTT domain. The row-by-row accumulation of b two-pass structure is illustrated in Figure 6 (Appendix A): Pass 1 (norm check, steps 1 – 6 in Figure 6) and Pass 2 (matrix–vector product, steps 7 – 17 ). Our implementation additionally introduces two caller-level unions that tightly pack all large temporaries into a fixed-size caller frame, eliminating the need for deep callee stack frames. The first union shares the 2 048-byte FFT scratch used for the singular-value norm in Pass 1 ( 3 , 5 ) with the 1 024-byte sampling polynomial (poly s) used in both passes ( 2 , 7 ); the FFT is invoked directly in the caller rather than delegated to a callee, so the scratch never appears as a separate stack frame. The second union shares the norm accumulator (int32_t sum[N], 1,024 B) in Pass 1 ( 1 ) with the row accumulator (poly b, 1,024 B) in Pass 2 ( 10 ), exploiting the strict lifetime disjointness across the two passes. Together, the two unions compress the dominant temporaries to 2 048 + 1 024 = 3 072 bytes in the caller frame, with no additional callee overhead for the norm computation. By analyzing the stack frames of each callee and identifying lifetime-disjoint buffers across the two passes, this union-based layout reduces the key-generation stack by approximately 400 B compared to [HCK+ 26] (4,784 B vs. 5,212 B on the same pqm4framework).
10
Low-Stack HAETAE for Memory-Constrained Microcontrollers
4.2
Low-stack signing via pass decomposition and reverse-order streaming
Recall HAETAE signing (Algorithm 5 in Appendix B) mainly consists of a rejectionsampling loop: each iteration draws ephemeral vectors (y1 , y2 ) from a hyperball distribution, b ◦ NTT(⌊y1 ⌉)) + 2⌊y2 ⌉ mod q, derives computes the matrix–vector product w ← NTT−1 (A b a challenge c, forms the response z = y + (−1) c ⋆ s, and repeats until the norm bounds are satisfied. The reference implementation [CCD+ 23] keeps w, z, and the hint h live simultaneously, leading to high peak stack usage. Our design follows the [BRS22] principle of trading recomputation for reduced peak memory, and adopts the seed-based on-the-fly matrix streaming used by [HCK+ 26]: each b is regenerated from the public seed rather than stored in RAM. Beyond these entry of A shared foundations, we introduce several techniques not described by [HCK+ 26]: (i) a Rejection-aware pass decomposition that confines encoding and hint computation to a post-acceptance path; (ii) Component-level early rejection that short-circuits the response computation in Pass B when a partial norm already exceeds the bound; and (iii) Reverseorder streaming entropy coding that eliminates full hint and high-bit staging buffers by aligning computation order with the rANS encoder’s backward symbol consumption. Additionally, our signing path achieves zero mutable BSS (.bss = 0 B) through a streaming Gaussian backend (Section 4.4). Moreover, while [HCK+ 26] targets HAETAE-5 only, our design supports all three security levels including HAETAE-2/3 (d>0). Figure 3 illustrates the resulting memory layout. Rejection-aware pass decomposition. We decompose the signing loop into three passes whose large buffers have strictly non-overlapping lifetimes: • Pass A (steps 1 – 8 in Figure 3) samples (y1 , y2 ) via the two-pass hyperball sampler (Section 4.4), computes w row by row using on-the-fly matrix streaming, derives w1′ = HBh (fromCRT(w, ⌊y1,1 ⌉)), and obtains the challenge c ← SampleBinaryChallengeτ H(w1′ , LSB(⌊y1,1 ⌉), µ) . The single-polynomial row accumulator for w reuses the output location of c (overwritten only at the end of the pass), eliminating a dedicated scratch buffer. For d>0 b is derived on-the-fly from the packed public (HAETAE-2/3), the first column of A key via in-place CRT reconstruction, requiring no additional polynomial buffer. • Pass B ( 9 – 11 ) regenerates (y1 , y2 ) from the stored seed and accepted nonce, computes z = y + (−1)b c ⋆ s one component at a time via fused accumulation (described below), and evaluates the rejection tests. No matrix product is needed, since the ℓ2 -norm and ℓ∞ tests involve only z, y, and b′ . Each component is discarded after its norm contribution is accumulated. • Pass C ( 12 – 14 ) runs only once, after acceptance. It recomputes z and w to derive the hint h ← w1′ − HBh (w′ − 2⌊z2 ⌉) mod + 2(q−1) and packs the signature. The αh variable-length payloads h and HBz1 (z1 ) are encoded via reverse-order streaming rANS (described below). Pass C is further split into two sub-phases (C1 , hint encoding, and C2 , z1 packing) with non-overlapping buffer lifetimes. Because the rejection loop comprises only Pass A and Pass B, all encoding and hint computation are deferred to the post-acceptance path. The peak signing stack is therefore Ssign = Sdriver + max SA , SB , SC1 , SC2 , (1) where Sdriver is the persistent driver state (seeds, nonce counter, hash prefix) and the four terms are the transient allocations of each pass. Our decomposition guarantees that the peak follows Equation (1) through explicit noinline boundaries between passes, confining encoding and hint computation to the single post-acceptance execution.
Gustavo Banegas, YoungBeom Kim, Seog Chung Seo and Christine van Vredendaal 11
In contrast, the idealized streaming baseline from Section 3 requires the full hint and high-bits arrays to be materialized before encoding: conv Ssign = (k+2) · |poly| + ℓ · N.
Our pass-aware design replaces this with Equation (1), where for HAETAE-5: SC1 ≈ 3 · |poly| + Bh ,
SC2 ≈ 2 · |poly| + Bhb ,
with Bh and Bhb denoting the compact streaming encoder buffers (bounded by the base entropy of h and HBz1 (z1 ) respectively), which are substantially smaller than the full staging arrays they replace. This means we are even below the idealized streaming baseline. Since SC1 and SC2 dominate the peak while Pass A requires only a single polynomial accumulator, the pass-aware structure leaves unused stack budget in Pass A. We exploit this by batching two matrix rows per iteration of the inner product, halving the number of ephemeral-vector regenerations from kℓ to ⌈k/2⌉ · ℓ at the cost of one additional polynomial accumulator (+1 024 B in SA ), without increasing the overall peak Ssign . Component-level early rejection. The reference implementation computes the full response vector z = (z1 , z2 ) before evaluating any rejection condition. We introduce component-level early exits that reduce the average cost of rejected iterations in Pass B (steps 9 – 10 in Figure 3). The first component z1,0 = y1,0 + (−1)b · c involves no secret-key material (the challenge c is derived from public data), so a data-dependent branch on its norm is constant-time safe. Pass B therefore computes z1,0 before any NTT-based multiplication ( 9 ) and rejects immediately if ∥z1,0 ∥2 > B12 (dashed arrow between 9 and 10 ), skipping the remaining ℓ+k−1 fused multiply-accumulate operations. During the P subsequent per-component norm accumulation ( 10 ) ∥z∥2 = i ∥zi ∥2 , we check the running partial sum after each polynomial and skip the remaining components once the bound is exceeded. Additionally, the hyperball scaling factors, which are deterministic functions of the seed and nonce counter, are computed once in the driver frame and passed by pointer to Passes B, C1 , and C2 , eliminating three redundant recomputations per accepted iteration. Reverse-order streaming entropy coding. The signature includes two variable-length rANS-encoded payloads: the hint h ∈ Zk×N and the high-bit decomposition HB(z1 ) ∈ Zℓ×N . Conventional implementations materialize these as full arrays before encoding; for HAETAE-5, a polyveck hint buffer (k× 1 024 B = 4 096 B) and an int8_t array (ℓ× N = 1 792 B) for HB(z1 ). rANS is a backward entropy coder: for a flat array X[0], . . . , X[m−1], the encoder consumes symbols in the order X[m−1], X[m−2], . . . , X[0]. The conventional approach first materializes the entire array, then iterates backward: RansEncPut(X[m−1]), RansEncPut(X[m−2]), . . . , RansEncPut(X[0]). We show that for a row-major R × C array (m = R · C), the identical reverse sequence can be produced without materializing the full array, by traversing rows from i = R−1 down to 0 and coefficients from j = C−1 down to 0 within each row: for i = R−1 downto 0 : for j = C−1 downto 0 : RansEncPut X[i · C + j] . This allows each coefficient to be fed to the encoder immediately upon computation, without materializing the full R × C array. In Pass C1 ( 12 in Figure 3), each hint row hi
12
Low-Stack HAETAE for Memory-Constrained Microcontrollers
(R=k, C=N ) is recomputed via row-streaming and immediately encoded; in Pass C2 ( 13 ), HBz1 (z1,i ) (R=ℓ, C=N ) is handled analogously. Both full staging buffers are eliminated entirely. The encoded output is accumulated in a compact stack-local encoder context and copied to the signature buffer only after encoding completes, following an internal encoding with copy-out boundary model. To verify correctness, we performed differential testing for each parameter set (HAETAE-2/3/5, 10 000 signatures each): for each randomly generated signature, we extracted h and HBz1 (z1 ) from the produced signature, re-encoded them with both the conventional full-array encoder (encode_h / encode_hb_z1) and the streaming reverse-order encoder, and compared the resulting byte streams. In all cases the two outputs were byte-identical. Incremental transcript hashing. Both signing (Pass A, steps 5 – 6 in Figure 3) and verification ( 8 – 9 in Figure 4) derive the challenge polynomial by hashing a transcript that includes the packed high bits of the matrix–vector product. The reference implementation allocates a contiguous buffer of POLYVECK_HIGHBITS_PACKEDBYTES + POLYC_PACKEDBYTES bytes (608–1 184 B depending on the security level), packs all k rows into it, and then feeds it to SHAKE256 in one shot. Because SHAKE256 is a sponge and satisfies absorb(A∥B) = absorb(A); absorb(B), we replace this monolithic buffer with row-byrow incremental absorb: each row’s high bits are packed into a small single-row buffer (POLY_HIGHBITS_PACKEDBYTES), immediately absorbed into the SHAKE256 state, and discarded before the next row is processed. After the row loop, the remaining fields (w′ and the message digest µ) are absorbed and the state is finalized. This eliminates the full transcript buffer entirely, yielding measurable stack savings (up to 656 B for HAETAE-5). Sparse challenge multiplication with fused accumulation. In Pass B ( 9 in Figure 3), Pτ for HAETAE-2/3, where the challenge c(X) = t=1 X it has Hamming weight τ =60, we replace NTT-based multiplication by a purely coefficient-domain signed shift-and-add rule in the negacyclic ring Rq = Zq [X]/(X N +1): (c ⋆ s)[j] =
τ X t=1
εt · s[(j − it ) mod N ],
( +1 εt = −1
j ≥ it , j < it ,
where εt arises from the negacyclic relation X N = −1. For HAETAE-5 (τ =128, dense binary challenge), we retain NTT-based multiplication as the dense weight makes a coefficient-domain approach less efficient. In all cases we fuse the accumulation directly into the response: each signed shift (or partial product) is added in place to the corresponding component of y, producing z without allocating a separate product polynomial (saving 1,024 B per multiplication). Algorithm-level BSS elimination. Our complete signing path uses no mutable BSS (.bss = 0 B). The hyperball sampler’s static temporary buffers (tmp_samples[N+1] and tmp_signs[(N+7)/8], totaling 2,088 B in the reference implementation) are replaced by a fully streaming Gaussian backend that generates samples on-the-fly from the SHAKE sponge state, as detailed in Section 4.4. Our implementation also provides an alternative build configuration (BRS_BSS_WORKSPACE) that places large signing vectors (y, z, Ay) in a static BSS workspace for reduced recomputation, trading BSS for lower-latency signing. In the full-streaming configuration (Table 3), the pass decomposition eliminates this workspace entirely, achieving .data = 0 and .bss = 0.
Gustavo Banegas, YoungBeom Kim, Seog Chung Seo and Christine van Vredendaal 13
32+32
|←−−−−→| w′ , ρ
512
|←−−→|
1024
|←−−−→|
1024
|←−−−→| 0
parse σ; extract ρ from pk
— Pre-pass: w′ and ∥z1 ∥2 — 0≤ℓ<L
hb_col
1 2
hb_col ← rANS_decode(σ, ℓ) z1,ℓ ← 28 · hb_col + lb[ℓ]
▷ ∥z1 ∥2 += ∥z1,ℓ ∥2 ; w′ ← LSB(z1,0 − c) — Row loop: r = 0 . . . K−1 —
hb_col
0≤ℓ<L
z1,ℓ
3
hb_col ← rANS_decode(σ, ℓ)
▷ re-decode per row (K× recomputation)
zb1,ℓ
4
tr
5
zb1,ℓ ← NTT(z1,ℓ ) b r,ℓ ◦ zb1,ℓ tr += A
b ▷ streamed A tr
6 0≤r<K
h_row ′ w1,r
z2,r
tr ← NTT−1 (tr )
▷ fromCRT lift to mod 2q 7
h_row ← rANS_decode(σ, r)
▷ reuses hb_col memory (union) h ′ ′ 8 w1,r ← HB (wr ) + h_row ′ 9 absorb pack(w1,r ) into H ▷ incremental transcript hashing ′ ′ 10 z2,r ← (αw1,r − tr + wr )/2 ▷ ∥z2 ∥2 += ∥z2,r ∥2 11 abort if ∥(z1 , z2 )∥2 > B
′
′ ′ ′ 12 c ← SampleBinaryChallengeτ (H(w1 , w , µ)) ′ ? 13 return (c = c)
Figure 4: Memory allocation of the row-streamed HAETAE verification. Four memory slots are used: persistent small buffers (w′ packed bits + seed ρ, 64 B, retained through the final challenge recomputation), a union{int8_t hb_col[N]; uint16_t h_row[N]} (512 B) that alternates between decoded high-bits columns in the inner ℓ loop and the decoded hint row afterwards, and two polynomials poly z and poly trow (1 024 B each). The row loop re-decodes HBz1 (z1 ) via streaming rANS for each row r, trading a factor-k re-computation for the elimination of a full polyveck buffer. The incremental SHAKE256 state H absorbs each row’s packed high bits immediately.
4.3
Low-stack verification via view-style decoding and row streaming
HAETAE verification (Algorithm 6 in Appendix C) reconstructs w̃1′ = h̃ + HBh (w̃′ ) from b ◦ NTT(z̃1 ) (up to the CRT lift mod 2q), derives the auxiliary component z̃2 , and rew̃ = A hashes the packed transcript (w̃1′ , w′ ) to recompute the challenge. Rather than following the column-streamed approach of [HCK+ 26], our verification is built on the [BRS22] method of trading re-computation for transient memory, combining (i) view-style decoding with union overlays, (ii) row-streamed matrix–vector multiplication, and (iii) incremental transcript hashing that eliminates the full-transcript buffer (the same technique introduced for signing in Section 4.2). This design supports all three security levels, including HAETAE-2/3 (D>0), which is not addressed by [HCK+ 26], and achieves a uniform verification stack of 3,800 B across all security levels, a 39 % reduction compared to the 6,220 B reported by [HCK+ 26] for HAETAE-5 alone. Figure 4 illustrates the resulting memory layout. View-style decoding. We avoid materializing the decoded signature vectors (steps 0 – 2 in Figure 4). Concretely, we keep LBz1 (⌊z1 ⌉) as a pointer into the signature buffer, decode only HBz1 (⌊z1 ⌉) into an int8 array ( 1 ), and decode h into a compact uint16 array ( 7 ). These two decoded arrays share a union overlay (int8_t hb_col[N] / uint16_t h_row[N]), exploiting lifetime disjointness: the high-bits columns are consumed during the inner column loop, after which the same memory is reused for the decoded hint row. We also represent w′ ∈ R2 as a packed bitstring of N/8 bytes. A pre-pass ( 1 – 2 ) over
14
Low-Stack HAETAE for Memory-Constrained Microcontrollers
coefficients recomposes z̃1,ℓ = HBz1 · 256 + LBz1 on-the-fly, accumulates ∥z̃1 ∥22 , and derives w′ = LSB(z̃1,1 − c). Together, the working set for decoded data is a single 512-byte union plus a 32-byte packed bitstring, independent of the module dimensions k and ℓ. Signatures that fail format checks (length, zero-padding, or rANS decoder errors) are rejected before any transcript recomputation. Row-streamed multiplication. To minimize peak stack, we compute w̃ one row at a time rather than column-by-column (steps 3 – 11 in Figure 4). For each output row r, PL−1 b we recompute an NTT-domain accumulator w̃r ← ℓ=0 A[r, ℓ] ◦ NTT(z̃1,ℓ ) ( 3 – 5 ) by b ℓ] from the (re)composing and transforming one column z̃1,ℓ at a time and streaming A[r, public seed ρ. After an inverse NTT and CRT lift via fromCRT ( 6 ), we decode the hint ′ row h̃r ( 7 ) and form w̃1,r = h̃r + HBh (w̃r′ ) ( 8 ), then immediately absorb the packed high bits into the incremental SHAKE256 transcript state ( 9 ). Within the same loop we compute z̃2,r ( 10 ), accumulate ∥z̃2,r ∥22 , and abort early as soon as the bound test fails ( 11 ). This reduces the working set to a constant number of polynomials plus small decoded arrays, eliminating concurrent polyveck temporaries. The tradeoff is a factor-k increase in re-computation: each row re-decodes the ℓ columns of HBz1 (⌊z1 ⌉) via streaming rANS and re-applies ℓ forward NTTs. In contrast, [HCK+ 26] uses a column-streamed approach that accumulates w̃ into a full polyveck buffer (k × 1 024 B) while sweeping the columns of z̃1 once. Our rowstreamed design trades this k-fold re-decode cost for a (k−1) × 1 024 B reduction in peak live memory. Combined with the incremental transcript hashing described in Section 4.2, which absorbs each row’s high bits directly into the SHAKE256 state, the full POLYVECK_HIGHBITS_PACKEDBYTES transcript buffer (up to 1 184 B) is eliminated entirely, an optimization not applied by either the reference implementation or [HCK+ 26]. b is derived on-the-fly from the public For D>0 (HAETAE-2/3), the first column of A seed and the packed public key, adding one polynomial expansion per row but no additional persistent storage. In the second pass, the sampler restarts the pseudorandom stream from the same (seed, nonce) pair, so that SampleGauss(st) reproduces the identical sequence (xi,j ). This time, each sample is immediately rescaled and rounded, y1,i,j = Round(αxi,j )
(0 ≤ i < ℓ),
y2,i,j = Round(αxℓ+i,j )
(0 ≤ i < k),
and written to the output polynomials y1 and y2 . The algorithm then evaluates the 2 squared norm (y1 , y2 ) 2 and rejects if it exceeds B02 Λ2 , repeating the entire two-pass procedure until acceptance.
4.4
A memory friendly sampler
The hyperball sampler is invoked in Pass A of signing ( 1 in Figure 3) to draw the ephemeral vectors (y1 , y2 ) used in each rejection-sampling iteration. We require a sampler that outputs a random vector (y1 , y2 ) ∈ Zℓ×N × Zk×N , whose distribution is (approximately) Gaussian, conditioned on the norm constraint (y1 , y2 ) 2 ≤ B0 Λ, for some bound B0 > 0 and scaling factor Λ (in our case Λ = ℓ+k). A naïve implementation samples all (ℓ + k)N Gaussian coefficients, stores them in memory, computes their squared norm, rescales the entire vector, and finally applies a rejection test. This requires Θ((ℓ+k)N ) words of transient storage. The two-pass approach that avoids this large buffer was first
Gustavo Banegas, YoungBeom Kim, Seog Chung Seo and Christine van Vredendaal 15
Algorithm 2 Streamed hyperball sampler Require: Gaussian dimension N , integers L, K; seed seed ∈ {0, 1}CRHBYTES ; nonce nonce ∈ {0, 1}16 ; hyperball bound B0 and scaling constant Λ (e.g. Λ = L + K) Ensure: (y1 , y2 ) ∈ ZL×N × ZK×N with ∥(y1 , y2 )∥2 ≤ B0 Λ 1: repeat 2: ▷ Pass 1: compute the (unnormalized) squared norm S 3: InitStream(st, seed, nonce) 4: S←0 ▷ S is a scalar accumulator (e.g. 64-bit integer) 5: for i ← 0 to L + K − 1 do 6: for j ← 0 to N − 1 do 7: xi,j ← SampleGauss(st) 8: S ← S + x2i,j 9: end for 10: end for B0 Λ 11: ▷ Compute scaling factor α ≈ √ S 12: α ← InvSqrt(S, B0 , Λ) 13: ▷ Pass 2: regenerate samples and scale immediately 14: InitStream(st, seed, nonce) 15: for i ← 0 to L − 1 do 16: for j ← 0 to N − 1 do 17: xi,j ← SampleGauss(st) 18: y1,i,j ← Round(α · xi,j ) 19: end for 20: end for 21: for i ← 0 to K − 1 do 22: for j ← 0 to N − 1 do 23: xL+i,j ← SampleGauss(st) 24: y2,i,j ← Round(α · xL+i,j ) 25: end for 26: end for 27: until ∥(y1 , y2 )∥22 ≤ B02 Λ2
described by [LWKP24] for BLISS and is also adopted by [HCK+ 26] for HAETAE-5. We apply the same high-level structure but further eliminate all static (BSS) scratch buffers through a fully streaming Gaussian backend. Algorithm 2 implements what we call the two-pass sampler with streaming Gaussian sampling and it only uses O(1) additional memory. The sampler is parameterized by a seed seed ∈ {0, 1}CRHBYTES and a nonce nonce, which are used to initialize a pseudorandom stream st (e.g. based on SHAKE or stream256). In the first pass, the algorithm draws (ℓ + k)N independent discrete Gaussian samples (xi,j )0≤i<ℓ+k, 0≤j<N from SampleGauss(st), and maintains only the scalar accumulator S =
ℓ+k−1 −1 X NX i=0
x2i,j .
j=0
No sample is stored beyond its contribution to S, so the memory footprint of this pass is independent of N , ℓ, and k. After the loop, the algorithm computes a scaling factor B0 Λ α≈ √ , S using a fixed-point approximation of the reciprocal square root. The following proposition proves that the two-pass streaming implementation produces an identical output distribution to the one-pass reference procedure using the same fixed-point InvSqrt routine.
16
Low-Stack HAETAE for Memory-Constrained Microcontrollers
Proposition 1. Conditioned on acceptance, the joint distribution of (y1 , y2 ) produced by Algorithm 2 is identical to that of the one-pass reference procedure that (i) draws all (L + K)NPGaussian samples into a single array, (ii) computes the scaling factor α = InvSqrt( x2i,j , B0 , Λ), (iii) maps each xi,j 7→ Round(αxi,j ), and (iv) accepts if and only if ∥(y1 , y2 )∥22 ≤ B02 Λ2 . Proof. Fix any seed and nonce. Since InitStream(st, seed, nonce) is deterministic and SampleGauss(st) is a pure function of the stream state, restarting the stream with the same (seed, nonce) P reproduces the identical sequence (xi,j ) in both passes. Consequently, the scalar S = i,j x2i,j and the scaling factor α = InvSqrt(S, B0 , Λ) computed in Pass 1 are identical to those that would be computed from the full array in the one-pass variant. The output coefficients Round(αxi,j ) and the acceptance predicate ∥(y1 , y2 )∥22 ≤ B02 Λ2 are therefore also identical. The two procedures thus define the same mapping from (seed, nonce) to (y1 , y2 ) (or to rejection), and hence the same conditional distribution given acceptance. Therefore the only difference is implementation strategy: the two-pass sampler never stores more than a bounded number of Gaussian samples at any one time. A further quantitative analysis of the fixed-point approximation error is left to future work. Streaming Gaussian backend. The reference HAETAE sampler allocates temporary arrays samples[N·(ℓ+k)] and signs[N·(ℓ+k)/8] in stack or BSS, requiring Θ((ℓ + k)N ) words of transient storage. Our implementation replaces this with a fully streaming backend: each discrete Gaussian sample is generated from the SHAKE sponge state, consumed, and discarded immediately. Since squeezing one sample at a time produces the identical output as batch squeezing, this has no effect on the output distribution. This eliminates all static sampler buffers, reducing the scheme-wide .bss to zero bytes.
5
Implementation and Evaluation
This section evaluates our low-stack HAETAE implementation. We report primary results on the pqm4 benchmarking framework [KPR+ ] (Nucleo-L4R5ZI, ARM Cortex-M4), which enables direct comparison with the prior work of [HCK+ 26] and with ML-DSA. We additionally validate portability under RIOT-OS on two further targets (nRF52840 and ESP32-C6).
5.1
Build configuration
Our implementation is controlled by three compile-time knobs: SAMPLER=2
STREAM_MATRIX=1
FROZEN_A=2
SAMPLER=2 selects the two-pass streaming hyperball sampler (Section 4.4); STREAM_MATRIX=1 regenerates matrix entries on demand from the public seed; and FROZEN_A=2 fuses rejection sampling with pointwise multiplication to eliminate temporary polynomial buffers. When all three are enabled, the full-streaming signing path (FULL_STREAM_SIGN) is activated automatically, applying the Rejection-aware pass decomposition and Reverse-order streaming entropy coding techniques described in Section 4.2.
5.2
Results on pqm4 framework (Nucleo-L4R5ZI)
All measurements are performed on the NUCLEO-L4R5ZI board (STM32L4R5ZI, ARM Cortex-M4F, 2 MB Flash, 640 kB RAM), the default pqm4 target and the platform used
Gustavo Banegas, YoungBeom Kim, Seog Chung Seo and Christine van Vredendaal 17 Table 3: Performance comparison on Nucleo-L4R5ZI (pqm4). Cycles: -O3, 20 MHz/0 WS, median of 100 runs (k = 103 ). Stack/size: -Os. Ratio relative to ref (<1: faster). (C) = pure C; (asm) = assembly. [HCK+ 26]: published numbers (HAETAE-5 only). ours (C)/ours (asm): this work. ML-DSA from pqm4; m4fstack followed [BRS22] strategy. Key generation Impl.
Cycles Ratio
Stack
Signing Cycles Ratio
Verification Stack
Cycles Ratio
Stack
.text
.total
HAETAE-2 ref (C) m4f (asm) ours (C) ours (asm)
9,253 k 6,980 k 11,630 k 11,518 k
1.00× 23,844 43,710 k 0.75× 19,772 18,616 k 1.26× 5,848 115,534 k 1.24× 5,816 81,416 k
1.00× 0.43× 2.64× 1.86×
73,112 55,684 5,968 5,968
1,732 k 998 k 1,417 k 1,071 k
1.00× 33,448 26,490 29,098 0.58× 23,296 30,104 30,624 0.82× 4,936 30,416 30,416 0.62× 4,824 38,100 38,100
HAETAE-3 ref (C) m4f (asm) ours (C) ours (asm)
12,007 k 13,584 k 20,998 k 21,889 k
1.00× 41,236 53,546 k 1.13× 29,484 28,275 k 1.75× 5,848 181,792 k 1.82× 5,920 138,771 k
1.00× 113,328 0.53× 83,436 3.40× 6,152 2.59× 6,152
3,170 k 1,909 k 2,897 k 2,134 k
1.00× 54,232 26,436 29,204 0.60× 31,776 30,078 30,758 0.91× 4,840 30,780 30,780 0.67× 4,840 38,464 38,464
HAETAE-5 ref (C) m4f (asm) [HCK+ 26] (C) ours (C) ours (asm)
16,491 k 20,115 k 15,328 k 11,561 k 10,423 k
1.00× 52,500 65,896 k 1.00× 144,408 1.22× 34,196 34,995 k 0.53× 103,988 0.93× 5,212 300,881 k 4.57× 8,092 0.70× 4,816 218,957 k 3.32× 6,136 0.63× 4,888 163,125 k 2.48× 6,136
3,968 k 2,532 k 4,187 k 3,510 k 2,736 k
1.00× 68,856 25,658 28,786 0.64× 37,292 29,756 30,796 1.06× 6,220 26,494 27,534 0.88× 4,840 30,150 30,150 0.69× 4,952 37,834 37,834
ML-DSA-44 m4f (asm) m4fstack (asm)
1,418 k 1.00× 38,312 1,797 k 1.27× 4,408
3,017 k 1.00× 10,330 k 3.42×
44,832 5,064
1,496 k 1.00× 3,816 k 2.55×
8,912 19,592 19,592 2,720 24,844 24,844
ML-DSA-65 m4f (asm) m4fstack (asm)
2,526 k 1.00× 60,840 3,422 k 1.35× 4,408
5,963 k 1.00× 21,668 k 3.63×
68,896 6,608
2,533 k 1.00× 6,771 k 2.67×
9,888 19,328 19,328 2,720 24,120 24,120
ML-DSA-87 m4f (asm) m4fstack (asm)
4,267 k 1.00× 97,704 5,770 k 1.35× 4,408
7,145 k 1.00× 107,912 4,381 k 1.00× 12,064 19,500 19,500 27,150 k 3.80× 8,144 11,713 k 2.67× 2,720 24,516 24,516
by [HCK+ 26]. Speed measurements use CLOCK_BENCHMARK (20 MHz, 0 WS flash) for cycleaccurate results; stack measurements use CLOCK_FAST (120 MHz). Stack measurements follow the pqm4 framework’s built-in stack-benchmarking infrastructure. Compiler optimization follows the pqm4 convention: -Os for stack and code-size measurements, -O3 for cycle-count benchmarks (separate builds). We report the median over 100 executions. All reported stack peaks are empirical measurements obtained with arm-none-eabi-gcc 11.3.1 under the default pqm4 build configuration (-Os, no link-time optimization). The noinline pass boundaries rely on compiler support for the __attribute__((noinline)) annotation. We benchmark four HAETAE configurations: ref (C) (latest C reference code [Kpq26]), m4f (asm) (pqm4 assembly, older spec [CCD+ 24]), ours (C) (this work, pure C), and ours (asm) (this work with assembly NTT and sampler from [CCD+ 24]). Both ours variants use the build knobs from Section 5.1. Since the implementation of [HCK+ 26] is not publicly available, we report their published numbers directly. Table 3 presents the results. Stack usage. Compared to the reference, ours (C) reduces peak Signing stack by 91.8– 95.8 % across all levels, bringing it to 5,968 B (HAETAE-2), 6,152 B (HAETAE-3), and 6,136 B (HAETAE-5). Verification stack ranges from 4,840 B to 4,936 B, an 85–93 % reduction. Key generation ranges from 4,816 B (HAETAE-5) to 5,848 B (HAETAE-2/3).
18
Low-Stack HAETAE for Memory-Constrained Microcontrollers
ours (asm) achieves comparable stack across all operations; the small differences (e.g. 4,824 B vs. 4,936 B for HAETAE-2 verification) reflect differing callee frame sizes in the assembly routines. Note that the m4f implementation is based on an older version of the specification and includes ARM assembly optimizations, so a direct comparison with our implementation is not entirely fair; we include it for completeness. For HAETAE-5, the only level reported by [HCK+ 26], our implementation achieves lower stack across all three operations: • Key generation: 4,816 B vs. 5,212 B (−7.6 %). Caller-level union analysis (Section 4.1) packs the FFT workspace and sampling scratch into shared memory slots. • Signing: 6,136 B vs. 8,092 B (−24 %). The pass decomposition with noinline boundaries (Section 4.2) ensures the peak is bounded by Sdriver + max(SA , SB , SC1 , SC2 ), and the Reverse-order streaming entropy coding eliminates the full hint and HBz1 staging buffers. • Verification: 4,840 B vs. 6,220 B (−22 %). Our row-streamed design (Section 4.3) replaces the column-streamed polyveck accumulator with a single polynomial, combined with view-style decoding and incremental transcript hashing. Both variants have .data = 0 and .bss = 0, whereas [HCK+ 26] reports a 1,040 B gap between .text and .total, whose breakdown is not disclosed. Cycle counts. Key generation for HAETAE-5 is 30 % faster than the reference in ours (C) (0.70×) and 37 % faster with ours (asm) (0.63×). Since d=0 key generation (Algorithm 4) performs the singular-value norm rejection before expanding the matrix A, with an acceptance rate of roughly 10 %, most iterations only execute the lightweight norm check, and the matrix–vector product runs only once after acceptance. For HAETAE-2/3 (d>0), the norm check is interleaved with the matrix–vector product, so each rejected sample also pays the streaming matrix cost, resulting in 1.24–1.82× slower key generation. Signature generation requires 1.86–3.40× the cycles of the reference (ours (C): 2.64– 3.40×; ours (asm): 1.86–2.59×), reflecting the cost of seed-based recomputation in every pass. For HAETAE-5, ours (C) achieves 218,957 k cycles, 27 % faster than [HCK+ 26] (300,881 k), with 24 % lower stack; Component-level early rejection (Section 4.2) reduces the average cost of rejected iterations by skipping unnecessary multiply-accumulate operations, contributing to this speedup. Ours (asm) further reduces this to 163,125 k (−46 % vs. [HCK+ 26]). Verification is faster than the reference at all levels for both variants (ours (C): 0.82– 0.91×; ours (asm): 0.62–0.69×). For HAETAE-5, [HCK+ 26] achieves 1.06× with 6,220 B stack, whereas ours (C) achieves 0.88× with 4,840 B, and ours (asm) reaches 0.69×. We attribute the speedup primarily to the smaller working set, which reduces memory traffic on the Cortex-M4. Code size. Ours (C) shows a modest .text increase compared to the reference (30,150 vs. 28,786 for HAETAE-5, +4.7 %), reflecting the streaming rANS encoder, fused multiplication, and pass decomposition logic. Ours (asm) is larger (37,834 for HAETAE-5, +31 % vs. ref) due to the inlined NTT and CDT sampler routines. Both variants place all constant tables in read-only memory, resulting in .data = 0 and .bss = 0; the reported .text and .total are therefore identical. ML-DSA scheme-only code sizes (19 kB to 24 kB) are smaller than HAETAE, reflecting the simpler structure of ML-DSA.
5.3
Results on RIOT-OS (nRF52840 and ESP32-C6)
To validate portability beyond the pqm4 bare-metal environment, we ran the same low-stack build under RIOT-OS [RIO] on two targets: the Nordic nRF52840 (ARM Cortex-M4F,
Gustavo Banegas, YoungBeom Kim, Seog Chung Seo and Christine van Vredendaal 19 Table 4: Low-stack evaluation on RIOT-OS (this work). nRF52840: ARM Cortex-M4F @ 64 MHz, 256 kB RAM. ESP32-C6: RISC-V RV32IMAC @ 80 MHz, 512 kB RAM. Cycles measured via xtimer function from RIOT-OS. Key generation
Signing
Cycles Stack
Cycles Stack Cycles Stack
HAETAE-2 nRF52840 29,039 k 5,988 ESP32-C6 49,371 k 6,100
262,721 k 6,096 2,023 k 3,984 476,223 k 6,068 3,619 k 4,004
Platform
Verification
HAETAE-3 nRF52840 46,520 k 6,208 829,928 k 6,288 3,838 k 3,984 ESP32-C6 80,811 k 6,580 1,519,566 k 6,260 7,146 k 4,004 HAETAE-5 nRF52840 13,612 k 5,096 ESP32-C6 21,513 k 5,254
193,913 k 6,406 4,970 k 3,976 526,047 k 6,244 9,536 k 4,004
Table 5: RAM budget for Verification and Signing (bytes). Verify total: |sig| + stack (public key in flash). Sign total: |sk| + |sig| + stack. Cycles: k = 103 , from pqm4 (Table 3). Verification Scheme
|pk|
|sk|
|sig| Stack Total
Cycles Stack
Signing Total
Cycles
HAETAE-2 (ours (C)) 992 1 408 1 474 4 936 6 410 HAETAE-3 (ours (C)) 1 472 2 112 2 349 4 840 7 189 HAETAE-5 (ours (C)) 2 080 2 752 2 948 4 840 7 788
1,417 k 5 968 8 850 115,534 k 2,897 k 6 152 10 613 181,792 k 3,510 k 6 136 11 836 218,957 k
HAETAE-5 [HCK+ 26]
4,187 k 8 092 13 792 300,881 k
2 080 2 752 2 948 6 220 9 168
ML-DSA-44 (m4fstack) 1 312 2 560 2 420 2 720 5 140 3,816 k 5 064 10 044 ML-DSA-65 (m4fstack) 1 952 4 032 3 309 2 720 6 029 6,771 k 6 608 13 949 ML-DSA-87 (m4fstack) 2 592 4 896 4 627 2 720 7 347 11,713 k 8 144 17 667
10,330 k 21,668 k 27,150 k
64 MHz, 256 kB RAM) and the Espressif ESP32-C6 (RISC-V RV32IMAC, 80 MHz, 512 kB RAM). Stack usage is measured via a high-watermark technique: the unused stack region below the current stack pointer is painted with a canary pattern before each operation, and the deepest overwrite is recorded after the operation returns. Timing uses RIOT’s xtimer layer converted to cycles via coreclock_hz. Results are averaged over 100 iterations. As Table 4 shows, peak stack figures are consistent between the two RIOT-OS targets. For HAETAE-2, signature generation peaks at 6,096 B (nRF52840) and 6,068 B (ESP32C6), confirming that the memory footprint is determined by the algorithm and build knobs, not by the ISA or OS layer.
Cycle-count gap between Cortex-M4F and RV32IMAC. Despite a 25 % higher clock frequency, the ESP32-C6 requires substantially more cycles for every operation. The slowdown is most pronounced for signing and other operations, the main reason is the absence of DSP/SIMD hardware on the in-order RV32IMAC core: the Cortex-M4F benefits from a single-cycle 32-bit multiplier suited to the NTT-heavy polynomial arithmetic in HAETAE.
20
6
Low-Stack HAETAE for Memory-Constrained Microcontrollers
Discussion
To provide a fair basis for comparison, the discussion below is based exclusively on pqm4 measurements (Table 3) using the same board, clock configuration, and measurement infrastructure for all schemes. Verification on 8 KB devices. On many constrained platforms, the public key is stored in flash memory, so the RAM budget for verification consists of the received signature plus the stack required to run the algorithm (Table 5), as is the case in, e.g., [BZB+ 22, BDKR23]. On devices with as little as 8 kB of SRAM, the available RAM is shared among .data, .bss, and the runtime stack, meaning that static data sections directly reduce the stack budget. Our implementation has .data = 0 and .bss = 0, leaving the full RAM available for the stack. In contrast, [HCK+ 26] reports a 1,040 B gap between .text and .total, but does not disclose the section-level breakdown. Ours (C) fits all three HAETAE security levels within 8 kB (6,410 B to 7,788 B), whereas [HCK+ 26] requires 9,168 B for HAETAE-5 verification alone. Compared to ML-DSA m4fstack, HAETAE verification is 2.34–3.34× faster at each comparable security level (1,417 k vs. 3,816 k at level 2, 2,897 k vs. 6,771 k at level 3, 3,510 k vs. 11,713 k at level 5). This makes HAETAE attractive for signature-verification-centric deployments such as firmware authentication and IoT attestation. Signature and key generation on 16 KB devices. For signing, the device must hold the secret key, the output signature, and the signing working set simultaneously (Table 5). All HAETAE levels fit within 16 kB (8,850 B to 11,836 B), while ML-DSA-87 exceeds this budget (17,667 B) due to the large secret key (4,896 B) and signing stack (8,144 B). At security level 5, HAETAE-5 requires 11,836 B for signing, roughly 5.7 kB less than ML-DSA-87. Key generation is comfortable for both schemes: our implementation requires at most 5,848 B of stack, well within the 16 kB budget.
References [BBC+ 23] Joppe W Bos, Olivier Bronchain, Frank Custers, Joost Renes, Denise Verbakel, and Christine van Vredendaal. Enabling FrodoKEM on embedded devices. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023(3):74–96, 2023. [BDKR23] Joppe W. Bos, Alexander Dima, Alexander Kiening, and Joost Renes. Postquantum secure over-the-air update of automotive systems. Cryptology ePrint Archive, Paper 2023/965, 2023. [BHG+ 13] Emmanuel Baccelli, Oliver Hahm, Mesut Günes, Matthias Wählisch, and Thomas C. Schmidt. RIOT OS: Towards an OS for the Internet of Things. In 2013 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 79–80, 2013. [BRS22]
Joppe W. Bos, Joost Renes, and Amber Sprenkels. Dilithium for memory constrained devices. In Lejla Batina and Joan Daemen, editors, Progress in Cryptology - AFRICACRYPT 2022: 13th International Conference on Cryptology in Africa, AFRICACRYPT 2022, Fes, Morocco, July 18-20, 2022, Proceedings, volume 13503 of Lecture Notes in Computer Science, pages 217–235. Springer Nature Switzerland, 2022.
Gustavo Banegas, YoungBeom Kim, Seog Chung Seo and Christine van Vredendaal 21
[BZB+ 22] Gustavo Banegas, Koen Zandberg, Emmanuel Baccelli, Adrian Herrmann, and Benjamin Smith. Quantum-resistant software update security on low-power networked embedded devices. In Giuseppe Ateniese and Daniele Venturi, editors, Applied Cryptography and Network Security - 20th International Conference, ACNS 2022, Rome, Italy, June 20-23, 2022, Proceedings, Lecture Notes in Computer Science, pages 872–891. Springer, 2022. [CCD+ 23] Jung Hee Cheon, Hyeongmin Choe, Julien Devevey, Tim Güneysu, Dongyeon Hong, Markus Krausz, Georg Land, Junbum Shin, Damien Stehlé, and MinJune Yi. HAETAE. Technical report, National Institute of Standards and Technology, 2023. available at https://csrc.nist.gov/Projects/pqc-dig-sig/ round-1-additional-signatures. [CCD+ 24] Jung Hee Cheon, Hyeongmin Choe, Julien Devevey, Tim Güneysu, Dongyeon Hong, Markus Krausz, Georg Land, Marc Möller, Damien Stehlé, and MinJune Yi. Haetae: Shorter lattice-based Fiat-Shamir signatures. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024(3):25–75, 2024. [HCK+ 26] Yulim Hyoung, Subeen Cho, Uijae Kim, Minwoo Lee, Hwajeong Seo, and Minjoo Sim. Memory-efficient implementation of SMAUG-T and HAETAE. Cryptology ePrint Archive, Paper 2026/442, 2026. [Kor]
Korean Post-Quantum Cryptography Research Group. KpqC Algorithms final specification documents. Accessed: 2026-03-30.
[Kpq26]
Korean Post-Quantum Cryptography Standardization Committee. HAETAE: Shorter Lattice-Based Fiat-Shamir Signatures, 2026. Final specification. available at https://www.kpqc.or.kr/images/pdf2/HAETAE.pdf.
[KPR+ ]
Matthias J. Kannwischer, Richard Petri, Joost Rijneveld, Peter Schwabe, and Ko Stoffelen. pqm4: Post-quantum crypto library for the ARM Cortex-M4. https://github.com/mupq/pqm4.
[LWKP24] Seungwoo Lee, Joo Woo, Jonghyun Kim, and Jong Hwan Park. Generalized centered binomial distribution for bimodal lattice signatures. IEEE Access, 13:2203–2214, 2024. [Lyu09]
Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In Mitsuru Matsui, editor, Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings, volume 5912 of Lecture Notes in Computer Science, pages 598–616. Springer, 2009.
[NIS23]
National Institute of Standards and Technology. Module-Lattice-Based Digital Signature Standard (ML-DSA), 2023. Federal Information Processing Standards Publication 204 (Initial Public Draft), https://doi.org/10.6028/NIST.FIPS. 204.ipd.
[RIO]
RIOT Community. Riot – the friendly operating system for the internet of things. Accessed: March 31, 2026.
22
A
Low-Stack HAETAE for Memory-Constrained Microcontrollers
Key Generation
Algorithm 3 KeyGen(1λ ) for d > 0
Algorithm 4 KeyGen(1λ ) for d = 0
Ensure: (pk, sk) 1: seed ← {0, 1}ρ0 2: (seedA , seedsk , K) ← Hgen (seed) b gen ) ← ExpandAd (seedA ) 3: (agen , A 4: (countersk , flag) ← (0, true) 5: while flag do 6: (sgen , egen ) ← ExpandS(seedsk , countersk ) b gen ◦ NTT(sgen )) + b ← agen + NTT−1 (A 7: egen mod q 8: (b0 , b1 ) ← (LowBitspk (b), HighBitspk (b)) 9: (s1 , s2 ) ← (sgen , egen − b0 ) 10: countersk ← countersk + 1 11: if N (s1 , s2 ) ≤ γ 2 n then 12: flag ← false 13: end if 14: end while 15: tr ← H(seedA , b1 ) 16: return (pk = (seedA , b1 ), sk = (s1 , s2 , K, tr, seedA , b1 ))
Ensure: (pk, sk) 1: seed ← {0, 1}ρ0 2: (seedA , seedsk , K) ← Hgen (seed) 3: (countersk , flag) ← (0, true) 4: while flag do 5: (sgen , egen ) ← ExpandS(seedsk , countersk ) 6: (s1 , s2 ) ← (sgen , egen ) 7: countersk ← countersk + 1 8: if N (s1 , s2 ) ≤ γ 2 n then 9: flag ← false 10: end if 11: end while b gen ← ExpandAd (seedA ) 12: A b b gen ◦ NTT(sgen ) + NTT(egen ) mod 13: b ← −2 A q 14: tr ← H(seedA , b b) 15: return (pk = (seedA , b b), sk = b (s1 , s2 , K, tr, seedA , b))
Figure 5: Implementation specification of HAETAE key generation [CCD+ 23, Kpq26]: d > 0 applies to HAETAE-2 and HAETAE-3, while d = 0 applies to HAETAE-5.
128
|←−−→| ρ, σ, K
1024
|←−−−→|
2048
|←−−−→| 0 reject
sum=0
N (sum) b b=0
sum ← 0 s1,j ← ExpandS(σ, j) 2 3 sum += ∥s1,j ∥ (in-place FFT) 4 s2,i ← ExpandS(σ, i) 2 5 sum += ∥s2,i ∥ (in-place FFT) 2 6 reject if N (sum) > γ N — Pass 2: compute b b — 7 s1,j ← ExpandS(σ, j) (re-sample) 8 write s1,j to sk (where i=0) 9 b s1,j ← NTT(s1,j ) b += A b i,j ◦ b b i,j ) 10 b s1,j (streamed A b ← fromMont(b) b 11 b 12 s2,i ← ExpandS(σ, i) 13 write s2,i to sk 14 b s2,i ← NTT(s2,i ) b←b b +b 15 b s2,i b ← −2b b 16 b b to pk (NTT domain) 17 write b 18 pack_remain_pk(ρ), pack_remain_sk(K) 1
s1,j FFT(s1,j ) s2,i FFT(s2,i )
s1,j
0≤j<ℓ
0≤i<k
0≤j<ℓ
b s1,j
s2,i b s2,i
0≤i<k
b b b b
b b b −2b
ρ, σ, K := Hgen (seed)
— Pass 1: norm check —
2
Figure 6: Memory allocation of HAETAE-5 Key generation (d=0). Two callerlevel unions share memory across passes: union{sum[N]; poly b} (1 024 B) and union{fft_input[FFT_N]; poly s} (2 048 B). Pass 1 checks the norm before expanding b Pass 2 computes b b = NTT(−2b). A;
Gustavo Banegas, YoungBeom Kim, Seog Chung Seo and Christine van Vredendaal 23
B
Signature Generation
Algorithm 5 Implementation Specification of HAETAE Signing [CCD+ 23, Kpq26] Require: sk = (s1 , s2 , K, tr, seedA , ψ), message M Ensure: signature σ b ← UnpackAd (seedA , ψ) 1: A 2: µ ← Hgen (tr, M ) 3: seedybb ← Hgen (K, µ) 4: (κ, σ) ← (0, ⊥) 5: while σ = ⊥ do 6: (y1 , y2 , b, b′ , κ) ← ExpandYbb(seedybb , κ) b ◦ NTT(⌊y1 ⌉)) + 2 · ⌊y2 ⌉ mod q 7: w ← NTT−1 (A ′ 8: w ← fromCRT(w, ⌊y1,1 ⌉) 9: w1′ ← HighBitsh (w′ ) 10: ρ ← H(w1′ , LSB(⌊y1,1 ⌉), µ) 11: c ← SampleBinaryChallengeτ (ρ) 12: b c ← NTT(c) 13: z1,1 ← y1,1 + (−1)b · c 14: (z1 )2..ℓ ← (y1 )2..ℓ + (−1)b NTT−1 (b c◦b s1 ) 15: z2 ← y2 + (−1)b NTT−1 (b c◦b s2 ) 16: if ∥(z1 , z2 )∥2 < B ′ and (∥2(z1 , z2 ) − (y1 , y2 )∥2 > B or b′ = 1) then 17: h ← w1′ − HighBitsh (w′ − 2⌊z2 ⌉) mod + 2(q−1) αh 18: σ ← PackSig(HighBitsz1 (⌊z1 ⌉), LowBitsz1 (⌊z1 ⌉), h, c) 19: end if 20: end while
C
Verification
Algorithm 6 Implementation Specification of HAETAE Verification [CCD+ 23, Kpq26] Require: pk = (seedA , ψ), message M , signature σ Ensure: Accept or Reject b ← UnpackAd (seedA , ψ) 1: A z z 2: (HighBits 1 (⌊z1 ⌉), LowBits 1 (⌊z1 ⌉), h, c) ← UnpackSig(σ) ▷ Can fail and rejection z1 z 3: z̃1 ← HighBits (⌊z1 ⌉) · 256 + LowBits 1 (⌊z1 ⌉) 4: w ′ ← LSB(z̃1,1 − c) b ◦ NTT(z̃1 ) mod q 5: w̃ ← A ′ 6: w̃ ← fromCRT(w̃, w ′ ) 2(q−1) h 7: w̃1′ ← h̃ + HighBits (w̃′ ) mod + α h 8: z̃2 ← [w̃1′ · αh + w ′ j − w̃′ mod 2q] / 2 ▷ Addition with w ′ only for first vector element 9: µ̃ ← Hgen (seedA , ψ, M ) 10: return (c = SampleBinaryChallengeτ (H(w̃1′ , w ′ , µ̃))) ∧ (∥(z̃1 , z̃2 )∥ < B ′′ )