Cryptology ePrint Archive: Report 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 exhaustive search of the key. The first one is a quantum variant of the table-based collision algorithm. The second one uses Kuperberg's abelian hidden shift algorithm in an offline manner. We show that the latter, although asymptotically promising, is not currently the most efficient against practical parameters.
Category / Keywords: secret-key cryptography / Legendre PRF, quantum cryptanalysis, quantum algorithms, Kuperberg's algorithm
Date: received 11 Feb 2021
Contact author: paul frixons at inria fr
Available format(s): PDF | BibTeX Citation
Version: 20210212:073753 (All versions of this report)
Short URL: ia.cr/2021/149
[ Cryptology ePrint archive ]