Quantum security of the Legendre PRF

MaRDI QIDQ7231684zbMATH OpenFDO

Authors Paul Frixons, André Schrottenloher

Publication date 22 April 2026

Published in Mathematical Cryptology (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://journals.flvc.org/mathcryptology/article/view/130578

zbMATH Keywords

abelian hidden shift problemKuperberg's algorithmLegendre PRFquantum algorithmsquantum cryptanalysis

Mathematics Subject Classification ID

Power residues, reciprocity (11A15) Number-theoretic algorithms; complexity (11Y16) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Cryptography (94A60)

Cites work

• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• An efficient quantum collision search algorithm and implications on symmetric cryptography
• An O(M(n) logn) Algorithm for the Jacobi Symbol
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Constructing elliptic curve isogenies in quantum subexponential time
• Cryptanalysis of the generalised Legendre pseudorandom function
• Efficient distributed quantum computing
• Grover meets Simon -- quantumly attacking the FX-construction
• He gives C-sieves on the CSIDH
• Hidden shift quantum cryptanalysis and implications
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• scientific article; zbMATH DE number 4187706 (Why is no real title available?)
• LegRoast: efficient post-quantum signatures from the Legendre PRF
• Quantum Algorithms for Some Hidden Shift Problems
• Quantum attacks without superposition queries: the offline Simon's algorithm
• Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE
• Quantum cryptanalysis of hash and claw-free functions
• Quantum resource estimates for computing elliptic curve discrete logarithms
• Quantum security analysis of CSIDH
• Quantum Walk Algorithm for Element Distinctness
• Strengths and Weaknesses of Quantum Computing
• The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound

Cited in

(1)

• The pseudorandomness of Legendre symbols under the quadratic-residuosity assumption

This page was built for publication: Quantum security of the Legendre PRF

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7231684)