Quantum Security of the Legendre PRF


Legendre PRF
quantum cryptanalysis
quantum algorithms
abelian hidden shift problem
Kuperberg’s algorithm

How to Cite

Frixons, P., & Schrottenloher, A. (2022). Quantum Security of the Legendre PRF. Mathematical Cryptology, 1(2), 52–69. Retrieved from https://journals.flvc.org/mathcryptology/article/view/130578


In this paper, we study the security of the Legendre PRF against quantum attackers, given classical queries only, and without quantum random-access memories. We give two algorithms that recover the key of a shifted Legendre symbol with unknown shift, with a complexity smaller than the exhaustive search of the key. The first one is a quantum variant of the table-based collision algorithm. The second one is an offline variant of Kuperberg’s abelian hidden shift algorithm. We note that the latter, although asymptotically promising, is not currently the most efficient against practical parameters.

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Copyright (c) 2022 Paul Frixons, André Schrottenloher