Paper 2021/149
Quantum Security of the Legendre PRF
Paul Frixons and André Schrottenloher
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Mathcrypt 2021
- Keywords
- Legendre PRFquantum cryptanalysisquantum algorithmsKuperberg's algorithm
- Contact author(s)
-
paul frixons @ inria fr
andre schrottenloher @ m4x org - History
- 2021-08-17: revised
- 2021-02-12: received
- See all versions
- Short URL
- https://ia.cr/2021/149
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/149,
author = {Paul Frixons and André Schrottenloher},
title = {Quantum Security of the Legendre {PRF}},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/149},
year = {2021},
url = {https://eprint.iacr.org/2021/149}
}
