Efficient Encoding and Random Sampling of Permutations

Uniformly sampling permutations over domains of size from 20 to 7000 is needed in many cryptographic systems, especially in code-based post-quantum cryptography, where permutations are part of private keys or digital signatures. A common way to uniformly sample a permutation is by using the Fisher-Yates shuffle algorithm, which is equivalent to obtaining the Lehmer digits of the permutation’s Lehmer representation. These digits are obtained by drawing random bits from a cryptographically secure pseudorandom number generator. If the drawn value is outside the valid range, it is rejected and new bits are sampled. Depending on the range of these digits, this sampling procedure can lead to a high rejection rate. In this paper, we propose methods that reduce the rejection rate and sample permutations more efficiently. The approach is based on encoding Lehmer digits in pairs or small groups and then drawing random bits to build these grouped digits. This reduces the number of discarded bits and provides a faster and more efficient way to sample uniform permutations compared to existing methods. As a byproduct, the proposed encoding methods also yield a more compact representation of permutations, requiring almost as few bits as the optimal encoding but with lower computational cost. Such a compact form is advantageous when the permutation itself, rather than a seed, is included in a signature, leading to reduced bandwidth usage.