.png){kind=icon}
.png){kind=icon}
Return
SoK: methods for sampling random permutations in post-quantum cryptography
.png){kind=icon}
PRE
AI
DOI：10.1080/23799927.2026.2651702.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Several hard problems in Post-quantum Cryptography, e.g. the Permuted Kernel Problem and the Linear Code Equivalence Problem, are constructed by applying a secret permutation to a geometrical or algebraic structure. The protocols that base their security on these hard problems, some of which have been submitted to the NIST competition for post-quantum digital signatures, require sampling permutations at random. This non-trivial computational task requires a dedicated, efficient, and secure implementation against side-channel attacks. Nevertheless, there is a lack of systematic research on this topic. Our work aims to bridge this gap by delving into a comprehensive study of the most prominent permutation sampling algorithms, evaluating both their strengths and limitations. First, we conduct a theoretical comparison of the algorithms present in the existing literature. Subsequently, we leverage our constant-time software C implementation (with and without AVX2 optimization) to draw practical conclusions, giving details on the performance and efficacy of these algorithms in real-world scenarios.
Keywords:
Fisher-Yates
permutation sampling
post-quantum cryptography
secure implementation
sorting
Journal
I
IF:
0.6
Papers:
10
Citations:
0