Welcome to the resource topic for 2024/412
Title:
Quasi-Optimal Permutation Ranking and Applications to PERK
Authors: Slim Bettaieb, Alessandro Budroni, Marco Palumbi, Décio Luiz Gazzoni Filho
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.
ePrint: https://eprint.iacr.org/2024/412
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .