Paper 2024/412
Quasi-Optimal Permutation Ranking and Applications to PERK
, Technology Innovation Institute, State University of Campinas, State University of LondrinaAbstract
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 CompressionPERKPermutation rankingPost-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}
}
