Paper 2024/008

SoK: Methods for Sampling Random Permutations in Post-Quantum Cryptography

Alessandro Budroni, Technology Innovation Institute
Isaac A. Canales-Martínez, Technology Innovation Institute
Lucas Pandolfo Perin, Technology Innovation Institute
Abstract

In post-quantum cryptography, permutations are frequently employed to construct cryptographic primitives. Careful design and implementation of sampling random unbiased permutations is essential for efficiency and protection against side-channel attacks. Nevertheless, there is a lack of systematic research on this topic. Our work seeks to fill this gap by studying the most prominent permutation sampling algorithms and assessing their advantages and limitations. We combine theoretical and experimental comparisons and provide a C library with the implementations of the algorithms discussed. Furthermore, we introduce a new sampling algorithm tailored for cryptographic applications.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
Fisher-YatesPermutation SamplingPost-quantum CryptographySecure ImplementationSoKSorting
Contact author(s)
alessandro budroni @ tii ae
isaac canales @ tii ae
lucas perin @ tii ae
History
2024-02-01: revised
2024-01-03: received
See all versions
Short URL
https://ia.cr/2024/008
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2024/008,
      author = {Alessandro Budroni and Isaac A. Canales-Martínez and Lucas Pandolfo Perin},
      title = {{SoK}: Methods for Sampling Random Permutations in Post-Quantum Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/008},
      year = {2024},
      url = {https://eprint.iacr.org/2024/008}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.