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

Abstract

We propose a heuristic algorithm to solve the underlying hard problem of the CSIDH cryptosystem (and other isogeny-based cryptosystems using elliptic curves with endomorphism ring isomorphic to an imaginary quadratic order 𝒪). Let Δ = Disc(𝒪) (in CSIDH, Δ = −4p for p the security parameter). Let 0 < α < 1/2, our algorithm requires:

Keywords

• isogenies
• imaginary quadratic orders
• quantum algorithms
• dihedral hidden subgroup problem
• csidh
• 94a60
• 68q12
• 68q15
• 81p68
• 11y16
• 14q05