Quasi-Optimal Permutation Ranking and Applications to PERK

ePrint Report: Quasi-Optimal Permutation Ranking and Applications to PERK

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

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 …

applications cryptographic eprint report function integer interest length maps marco report size