Journal ArticleA trade-off between classical and quantum circuit size for an attack against CSIDHBiasse, Jean-François; Bonnetain, Xavier; Pring, Benjamin; Schrottenloher, André; Youmans, WilliamnullAbstract 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, Δ = −4 p for p the security parameter). Let 0 < α < 1/2, our algorithm requires: A classical circuit of size 2 O ˜ log ( | Δ | ) 1 − α . $2^{\tilde{O}\left(\log(|\Delta|)^{1-\alpha}\right)}.$ A quantum circuit of size 2 O ˜ log ( | Δ | ) α . $2^{\tilde{O}\left(\log(|\Delta|)^{\alpha}\right)}.$ Polynomial classical and quantum memory. Essentially, we propose to reduce the size of the quantum circuit below the state-of-the-art complexity 2 O ˜ log ( | Δ | ) 1 / 2 $2^{\tilde{O}\left(\log(|\Delta|)^{1/2}\right)}$ at the cost of increasing the classical circuit-size required. The required classical circuit remains subexponential, which is a superpolynomial improvement over the classical state-of-the-art exponential solutions to these problems. Our method requires polynomial memory, both classical and quantum.2020-11-1710295503Journal of Mathematical Cryptology1514 to 171862-2984https://doi.org/10.1515/jmc-2020-00701839805National Science Foundation