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

Journal of mathematical cryptology

article

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

[1] University of South Florida, United States of America;INRIA

关键词: Isogenies;    Imaginary quadratic orders;    Quantum algorithms;    Dihedral Hidden Subgroup Problem;    CSIDH;   

DOI  :  10.1515/jmc-2020-0070

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

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 2O˜log(|Δ|)1−α. $2^{\tilde{O}\left(\log(|\Delta|)^{1-\alpha}\right)}.$ A quantum circuit of size 2O˜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 2O˜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.

【 授权许可】

CC BY|CC BY-NC-ND