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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2021/149}},
      url = {https://eprint.iacr.org/2021/149}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.