Quasi-Optimal Permutation Ranking and Applications to PERK

Slim Bettaieb; Alessandro Budroni; Marco Palumbi; Décio Luiz Gazzoni Filho

Paper 2024/412

Quasi-Optimal Permutation Ranking and Applications to PERK

Slim Bettaieb, Technology Innovation Institute

Alessandro Budroni

, Technology Innovation Institute

Marco Palumbi, Technology Innovation Institute

Décio Luiz Gazzoni Filho

, State University of Campinas, State University of Londrina

Abstract

A ranking function for permutations maps every permutation of length $n$ to a unique integer between $0$ and $n! - 1$ . For permutations of size that are of interest in cryptographic applications, evaluating such a function requires multiple-precision arithmetic. This work introduces a quasi-optimal ranking technique that allows us to rank a permutation efficiently without needing a multiple-precision arithmetic library. We present experiments that show the computational advantage of our method compared to the standard lexicographic optimal permutation ranking. As an application of our result, we show how this technique improves the signature sizes and the efficiency of PERK digital signature scheme.

Note: Added link to repository.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. Minor revision. AfricaCrypt 2024
Keywords: Efficient Compression PERK Permutation ranking Post-quantum Cryptography
Contact author(s): slim bettaieb @ tii ae
budroni alessandro @ gmail com
marco palumbi @ tii ae
decio gazzoni @ ic unicamp br
History: 2024-05-13: revised; 2024-03-07: received; See all versions
Short URL: https://ia.cr/2024/412
License: CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2024/412,
      author = {Slim Bettaieb and Alessandro Budroni and Marco Palumbi and Décio Luiz Gazzoni Filho},
      title = {Quasi-Optimal Permutation Ranking and Applications to {PERK}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/412},
      year = {2024},
      url = {https://eprint.iacr.org/2024/412}
}