Sota Voce: Low-Noise Sampling of Sparse Fixed-Weight Vectors

Many post-quantum cryptosystems require generating an n-bit binary vector with a prescribed Hamming weight ω, a process known as fixed-weight sampling. When ω = O(n), we call this dense fixed-weight sampling, which commonly appears in lattice-based cryptosystems, like those in the NTRU family. In contrast, code-based cryptosystems typically use sparse fixed-weight sampling with ω = o(n) (e.g., O(√n). Sparse fixed-weight sampling generally involves three constant-time steps to keep the sampled vector secret: 1. sample ω nearly uniform random integers from a series of decreasing intervals; 2. map these integers into a set of ω distinct indices in [0, n), called the support; 3. generate a binary n-bit vector with bits set only at the support indices. Remarkably, some of the core algorithms employed in fixed-weight sampling date back to nearly a century, yet developing efficient and secure techniques remains essential for modern post-quantum cryptographic applications. In this paper, we present novel algorithms for steps two and three of the fixedweight sampling process. We demonstrate their practical applicability by replacing the current fixed-weight sampling routine in the HQC post-quantum key exchange mechanism, recently selected for NIST standardization. We rigorously prove that our procedures are sound, secure, and introduce little to no bias. Our implementation of the proposed algorithms accelerates step 2 by up to 2.9x and step 3 by up to 5.8x compared to an optimized version of the fixed-weight sampler currently used in HQC. Since fixed-weight sampling constitutes a significant portion of HQC’s execution time, these speedups translate into protocol-level improvements of up to 1.37x, 1.28x and 1.21x for key generation, encapsulation and decapsulation, respectively.