---
title: "quantica — Memory Consumption Analysis"
subtitle: "Stack and Heap usage for ML-KEM, ML-DSA, SLH-DSA"
author: "krypteia project"
date: "2026-04-12"
geometry: margin=2cm
fontsize: 11pt
colorlinks: true
header-includes:
- \usepackage{booktabs}
- \usepackage{longtable}
- \usepackage{xcolor}
- \definecolor{cyan}{HTML}{00B4D8}
- \definecolor{green}{HTML}{2DC653}
- \definecolor{red}{HTML}{E63946}
- \usepackage{draftwatermark}
- \SetWatermarkText{CONFIDENTIAL}
- \SetWatermarkScale{0.5}
- \SetWatermarkColor[gray]{0.85}
- \SetWatermarkAngle{45}
---
# Executive summary
The `quantica` crate implements the three NIST post-quantum cryptographic
standards (ML-KEM, ML-DSA, SLH-DSA) in pure Rust. This document analyzes
the RAM consumption (stack + heap) of each algorithm at each security
level, with and without the `sca-protected` side-channel countermeasures.
**Key findings:**
- **ML-KEM** is the lightest: peak ~20 KB (keygen/encaps), fits
comfortably on Cortex-M0 (8--32 KB SRAM).
- **ML-DSA Sign with SCA masking** is the heaviest: peak ~93 KB,
requiring at least a Cortex-M4 class device (64+ KB SRAM).
- **SLH-DSA** has minimal stack usage (~2 KB) but allocates large
signatures on the heap (up to 50 KB for SHAKE-256f).
- No problematic recursion exists in the codebase.
\newpage
# 1. ML-KEM (FIPS 203)
## Arithmetic characteristics
| Coefficient type | `i16` (2 bytes) |
| Modulus $q$ | 3329 |
| Polynomial degree $N$ | 256 |
| Polynomial size | $256 \times 2 = 512$ bytes |
| Max module rank $k$ | 4 (ML-KEM-1024) |
| Matrix $\hat{A}$ size | $k^2 \times 512 = 8{,}192$ bytes |
## Stack usage per operation
| **KeyGen** | $\hat{A}$ (8 KB) + $\hat{s}$, $\hat{e}$, $\hat{t}$ (6 KB) | **~14.5 KB** | |
| **KeyGen SCA** | + MaskedPoly for $\hat{s}$ (1 KB) | **~15.5 KB** | Shuffled NTT adds negligible stack |
| **Encaps (encrypt)** | $\hat{A}$ (8 KB) + $\hat{y}$, $e_1$, $e_2$, $u$, $v$ (9.6 KB) | **~17.6 KB** | Heaviest ML-KEM operation |
| **Decaps (decrypt)** | $u$ (2 KB) + $\hat{s}$, $v$, acc, $w$ (3.6 KB) | **~5.6 KB** | |
| **Decaps SCA** | + MaskedPoly acc (1 KB) | **~6.6 KB** | |
## Heap usage per operation
| KeyGen | `ek: Vec<u8>` | 1,184 B | 1,568 B |
| KeyGen | `dk: Vec<u8>` | 2,400 B | 3,168 B |
| Encaps | `ct: Vec<u8>` | 1,088 B | 1,568 B |
| Decaps | (none) | 0 | 0 |
## Total peak RAM by parameter set
| ML-KEM-512 | ~16 KB | ~19 KB | ~6 KB | ~7 KB |
| ML-KEM-768 | ~18 KB | ~20 KB | ~6 KB | ~7 KB |
| ML-KEM-1024 | ~19 KB | ~22 KB | ~6 KB | ~7 KB |
\newpage
# 2. ML-DSA (FIPS 204)
## Arithmetic characteristics
| Coefficient type | `i32` (4 bytes) |
| Modulus $q$ | 8,380,417 |
| Polynomial degree $N$ | 256 |
| Polynomial size | $256 \times 4 = 1{,}024$ bytes |
| Max rank $k$ (rows) | 8 (ML-DSA-87) |
| Max rank $l$ (columns) | 7 (ML-DSA-87) |
| Array `[[i32; N]; MAX_K]` | $8 \times 1{,}024 = 8{,}192$ bytes |
| Array `[[i32; N]; MAX_L]` | $7 \times 1{,}024 = 7{,}168$ bytes |
## Stack usage per operation
### KeyGen
| `s1_hat` | `[[i32; 256]; MAX_L]` | 7,168 B |
| `s2` | `[[i32; 256]; MAX_K]` | 8,192 B |
| `t` | `[[i32; 256]; MAX_K]` | 8,192 B |
| `tmp` | `[[i32; 256]; MAX_K]` | 8,192 B |
| Seeds + hashes | | ~300 B |
| **Total** | | **~32 KB** |
### Sign (standard, without SCA)
| `s1_hat` | `[MAX_L]` | 7,168 B | whole function |
| `s2_hat` | `[MAX_K]` | 8,192 B | whole function |
| `t0_hat` | `[MAX_K]` | 8,192 B | whole function |
| `y` | `[MAX_L]` | 7,168 B | per iteration |
| `y_hat` | `[MAX_L]` | 7,168 B | per iteration |
| `w` | `[MAX_K]` | 8,192 B | per iteration |
| `w1` | `[MAX_K]` | 8,192 B | per iteration |
| `cs1` | `[MAX_L]` | 7,168 B | per iteration |
| `z` | `[MAX_L]` | 7,168 B | per iteration |
| `cs2` | `[MAX_K]` | 8,192 B | per iteration |
| `w_minus_cs2` | `[MAX_K]` | 8,192 B | per iteration |
| `r0` | `[MAX_K]` | 8,192 B | per iteration |
| `ct0` | `[MAX_K]` | 8,192 B | per iteration |
| `neg_ct0` | `[MAX_K]` | 8,192 B | per iteration |
| `w_cs2_ct0` | `[MAX_K]` | 8,192 B | per iteration |
| `c`, `c_hat` | `[i32; 256]` | 2,048 B | per iteration |
| **Total** | | **~55 KB** | |
### Sign SCA (with masking)
Adds three masked arrays to the above:
| `s1m` | `[MaskedPoly; MAX_L]` | $7 \times 2{,}048 = 14{,}336$ B |
| `s2m` | `[MaskedPoly; MAX_K]` | $8 \times 2{,}048 = 16{,}384$ B |
| `t0m` | `[MaskedPoly; MAX_K]` | $8 \times 2{,}048 = 16{,}384$ B |
| **Additional masking overhead** | | **~46 KB** |
| **Sign SCA total** | | **~88--93 KB** |
Note: `MaskedPoly` = `{ share0: [i32; 256], share1: [i32; 256] }` = 2,048 bytes per instance.
### Verify
| `z_hat` | `[MAX_L]` | 7,168 B |
| `t1_2d_hat` | `[MAX_K]` | 8,192 B |
| `az` | `[MAX_K]` | 8,192 B |
| `ct1` | `[MAX_K]` | 8,192 B |
| `w_approx` | `[MAX_K]` | 8,192 B |
| Seeds + hashes | | ~200 B |
| **Total** | | **~42 KB** |
## Heap usage
| KeyGen | `pk: Vec<u8>` | 2,592 B |
| KeyGen | `sk: Vec<u8>` | 4,896 B |
| Sign | `sig: Vec<u8>` | 4,627 B |
| Verify | `c_tilde: Vec<u8>` | 64 B |
## Total peak RAM by parameter set
| ML-DSA-44 ($k$=4, $l$=4) | ~20 KB | ~35 KB | ~58 KB | ~25 KB |
| ML-DSA-65 ($k$=6, $l$=5) | ~28 KB | ~48 KB | ~78 KB | ~35 KB |
| ML-DSA-87 ($k$=8, $l$=7) | ~40 KB | ~60 KB | ~93 KB | ~42 KB |
Note: actual stack usage is lower than the theoretical maximum because
the arrays are dimensioned for MAX_K/MAX_L at compile time, but only
the first $k$/$l$ elements are used at runtime.
\newpage
# 3. SLH-DSA (FIPS 205)
## Arithmetic characteristics
SLH-DSA is purely hash-based: no polynomials, no NTT. Stack usage is
dominated by the ADRS address structure (32 bytes) and small local
buffers. All significant data is heap-allocated.
| Security parameter $n$ | 16 B | 24 B | 32 B |
| FORS trees $k$ | 14 / 33 | 22 / 33 | 22 / 35 |
| FORS height $a$ | 12 / 6 | 6 / 8 | 8 / 9 |
| XMSS height $h'$ | 7 / 3 | 7 / 3 | 8 / 4 |
| Total tree height $h$ | 63 / 66 | 63 / 66 | 64 / 68 |
## Stack usage
All operations use **~1--2 KB** of stack (ADRS + seed buffers + loop
variables). No large polynomial arrays.
## Heap usage per operation
| KeyGen | sk (4$n$) + pk (2$n$) | 96 B | 192 B |
| Sign | `sig: Vec<u8>` | 17,088 B | 49,856 B |
| Sign | `fors_sig` | ~3,168 B | ~11,200 B |
| Sign | `nodes` (FORS tree) | ~2 KB | ~16 KB |
| Verify | (reads sig, no large alloc) | ~1 KB | ~1 KB |
## Total peak RAM
| SHAKE-128s | ~1 KB | ~25 KB | ~10 KB |
| SHAKE-128f | ~1 KB | ~30 KB | ~20 KB |
| SHAKE-256s | ~1 KB | ~45 KB | ~35 KB |
| SHAKE-256f | ~1 KB | ~65 KB | ~50 KB |
\newpage
# 4. Target compatibility matrix
| **Cortex-M0** (8 KB SE) | 8 KB | Encaps tight | \textcolor{red}{Too large} | \textcolor{red}{No} | KeyGen only |
| **Cortex-M0** (STM32F0) | 8--32 KB | \textcolor{green}{OK} | Tight (44 only) | \textcolor{red}{No} | \textcolor{green}{OK} (128s) |
| **Cortex-M4** (STM32F4) | 64--256 KB | \textcolor{green}{OK} | \textcolor{green}{OK} | \textcolor{green}{OK} | \textcolor{green}{OK} |
| **Cortex-M33** (STM32U5) | 256--768 KB | \textcolor{green}{OK} | \textcolor{green}{OK} | \textcolor{green}{OK} | \textcolor{green}{OK} |
| **ESP32-C3** (RISC-V) | 400 KB | \textcolor{green}{OK} | \textcolor{green}{OK} | \textcolor{green}{OK} | \textcolor{green}{OK} |
| **Desktop / Wasm** | MB+ | Trivial | Trivial | Trivial | Trivial |
# 5. Optimization opportunities
## 5.1 ML-DSA stack reduction
**Problem:** Arrays are dimensioned `[MAX_K]` / `[MAX_L]` (compile-time
worst case), but at runtime only `k` / `l` elements are used.
**Proposal:** Make the stack arrays const-generic on the parameter set
rather than using MAX_K/MAX_L. This would reduce ML-DSA-44 Sign from
~35 KB to ~22 KB (K=4 instead of MAX_K=8).
**Effort:** Medium — requires propagating `K` and `L` as const generics.
## 5.2 ML-DSA SCA sequential masking
**Problem:** Sign SCA allocates all three masked vectors (s1m, s2m, t0m)
simultaneously: +46 KB.
**Proposal:** Mask s1/s2/t0 one at a time, reusing the same buffer.
The rejection loop needs all three, but the initial shuffled NTT +
masking could be done sequentially (NTT then mask into a single
`MaskedPoly` array, then swap).
**Effort:** Medium — requires restructuring the SCA block in `sign_internal`.
## 5.3 Heap elimination (`Vec<u8>` → caller-provided buffers)
**Problem:** All key/ciphertext/signature outputs are `Vec<u8>`,
requiring an allocator.
**Proposal:** Offer an alternative API:
`fn keygen_into(rng, ek: &mut [u8], dk: &mut [u8]) -> Result<(), Error>`
**Effort:** High — touches every public function, tests, FFI, wasm.
## 5.4 SLH-DSA FORS tree allocation
**Problem:** `fors_node()` allocates `2^a` node buffers on the heap
(up to 512 × 32 = 16 KB for SHAKE-256f).
**Proposal:** Use a fixed-size stack buffer for the tree computation
(max 512 × 32 = 16 KB, or iterate level-by-level with 2 buffers).
**Effort:** Low--Medium.
# 6. Recursion analysis
| `wots.rs` | `chain()` | Yes | ~15 | ~64 B (~1 KB total) |
| `wots.rs` | `chain_iter()` | No (iterative) | -- | -- |
| `xmss.rs` | `xmss_node()` | No (iterative) | -- | -- |
| `fors.rs` | `fors_node()` | No (iterative) | -- | -- |
| `hypertree.rs` | `ht_sign/verify` | No (loop over layers) | -- | -- |
**Conclusion:** No dangerous recursion. The only recursive function
(`chain()`) has bounded depth (~15) and minimal frame size. The
production code path uses `chain_iter()` (iterative) in most places.