Paper 2019/725

He Gives C-Sieves on the CSIDH

Chris Peikert

Abstract

Recently, Castryck, Lange, Martindale, Panny, and Renes proposed CSIDH (pronounced "sea-side") as a candidate post-quantum "commutative group action." It has attracted much attention and interest, in part because it enables noninteractive Diffie--Hellman-like key exchange with quite small communication. Subsequently, CSIDH has also been used as a foundation for digital signatures. In 2003--04, Kuperberg and then Regev gave asymptotically subexponential quantum algorithms for "hidden shift" problems, which can be used to recover the CSIDH secret key from a public key. In late 2011, Kuperberg gave a follow-up quantum algorithm called the collimation sieve ("c-sieve" for short), which improves the prior ones, in particular by using exponentially less quantum memory and offering more parameter tradeoffs. While recent works have analyzed the concrete cost of the original algorithms (and variants) against CSIDH, nothing of this nature was previously available for the c-sieve. This work fills that gap. Specifically, we generalize Kuperberg's collimation sieve to work for arbitrary finite cyclic groups, provide some practical efficiency improvements, give a classical (i.e., non-quantum) simulator, run experiments for a wide range of parameters up to and including the actual CSIDH-512 group order, and concretely quantify the complexity of the c-sieve against CSIDH. Our main conclusion is that the proposed CSIDH-512 parameters provide relatively little quantum security beyond what is given by the cost of quantumly evaluating the CSIDH group action itself (on a uniform superposition). The cost of key recovery is, for example, only about $2^{16}$ quantum evaluations using $2^{40}$ bits of quantumly accessible classical memory (plus insignificant other resources). This improves upon a prior estimate of $2^{32.5}$ evaluations and $2^{31}$ qubits of quantum memory, for a variant of Kuperberg's original sieve. Under the plausible assumption that quantum evaluation does not cost much more than is indicated by a recent "best case" analysis, CSIDH-512 can therefore be broken using significantly less than $2^{64}$ quantum T-gates (plus relatively small other resources). This falsifies a standard interpretation of the claimed $64$ bits of quantum security, and it strongly invalidates the claimed NIST security level 1 when accounting for the MAXDEPTH restriction.

Note: Added cost analysis for QRACM, additional references, other clarifications