Module shuffle 

Fisher-Yates shuffle for NTT butterfly index randomization (SPA protection). Fisher-Yates shuffle for NTT butterfly index randomization (countermeasure: SPA / SEMA on secret-polynomial NTT).

Principle

Butterflies at the same NTT level are mutually independent: permuting their execution order does not change the output polynomial, only the pattern of memory accesses and instantaneous power consumption. By drawing a fresh permutation on every invocation from a CSPRNG seeded with per-signature entropy, two successive NTTs on the same input produce different power / EM traces, defeating trace-alignment-based SPA and template attacks.

The permutation is drawn with rejection sampling on a 16-bit RNG output so the sampled indices are unbiased.

References

• J. Aycock et al., Hardware NTT shuffling as a lightweight countermeasure for ML-KEM (arXiv, 2024) — baseline hardware construction we re-implement in software.
• M.-J. O. Saarinen, Practical side-channel evaluation of post- quantum primitives (NIST, 2023) — independent evaluation of the shuffling benefit on ML-KEM / ML-DSA.

Where to look next

• Countermeasure description and threat analysis: doc/sca/countermeasures/ml_kem.rst, section SPA / SEMA — NTT butterfly shuffling.
• Call sites: quantica/src/ml_kem/kem.rs, functions keygen_internal_sca and decaps_internal_sca.
• Companion primitive reference: doc/sca/primitives.rst.

Functions

generate_permutation

Generate a uniform random permutation of 0..n using Fisher-Yates.

ntt_shuffled

Forward NTT with randomized butterfly ordering (SPA countermeasure).