A trade-off between classical and quantum circuit size for an attack against CSIDH

DOI10.1515/jmc-2020-0070zbMath1464.94028OpenAlexW3035865612MaRDI QIDQ2027261

André Schrottenloher, Benjamin Pring, Jean-François Biasse, William Youmans, Xavier Bonnetain

Publication date: 25 May 2021

Published in: Journal of Mathematical Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/jmc-2020-0070

zbMATH Keywords

quantum algorithmsisogeniesCSIDHdihedral hidden subgroup problemimaginary quadratic orders

Mathematics Subject Classification ID

Quantum computation (81P68) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Computational aspects of algebraic curves (14Q05) Applications to coding theory and cryptography of arithmetic geometry (14G50) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum cryptography (quantum-theoretic aspects) (81P94)

Related Items (2)

Hybrid decoding -- classical-quantum trade-offs for information set decoding ⋮ Quantum security analysis of CSIDH

Cites Work

• Unnamed Item
• Unnamed Item
• Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves
• Expander graphs based on GRH with an application to elliptic curve cryptography
• Cryptographic hash functions from expander graphs
• Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3
• CSIDH: an efficient post-quantum commutative group action
• A note on the security of CSIDH
• Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE
• Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies
• Applying Grover’s Algorithm to AES: Quantum Resource Estimates
• A Quantum Algorithm for Computing Isogenies between Supersingular Elliptic Curves
• Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Evaluating Large Degree Isogenies and Applications to Pairing Based Cryptography
• Time/Space Trade-Offs for Reversible Computation
• Resilient quantum computation: error models and thresholds
• Constructing elliptic curve isogenies in quantum subexponential time
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

This page was built for publication: A trade-off between classical and quantum circuit size for an attack against CSIDH