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

Alessandro Budroni; Isaac A. Canales-Martínez; Lucas Pandolfo Perin

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-Yates Permutation Sampling Post-quantum Cryptography Secure Implementation SoK Sorting
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: 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},
      note = {\url{https://eprint.iacr.org/2024/008}},
      url = {https://eprint.iacr.org/2024/008}
}