International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

He Gives C-Sieves on the CSIDH

Authors:
Chris Peikert , University of Michigan
Download:
DOI: 10.1007/978-3-030-45724-2_16 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: Recently, Castryck, Lange, Martindale, Panny, and Renes proposed \emph{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 \emph{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 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 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). For example, the cost of CSIDH-512 key recovery is only about~$2^{16}$ quantum evaluations using~$2^{40}$ bits of quantumly accessible \emph{classical} memory (plus relatively small other resources). This improves upon a prior estimate of~$2^{32.5}$ evaluations and~$2^{31}$ qubits of \emph{quantum} memory, for a variant of Kuperberg's original sieve. Under the plausible assumption that quantum evaluation does not cost much more than what is given by a recent ``best case'' analysis, CSIDH-512 can therefore be broken using significantly less than~$2^{64}$ quantum T-gates. This strongly invalidates its claimed NIST level~1 quantum security, especially when accounting for the MAXDEPTH restriction. Moreover, under analogous assumptions for CSIDH-1024 and -1792, which target higher NIST security levels, except near the high end of the MAXDEPTH range even these instantiations fall short of level~1.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30240,
  title={He Gives C-Sieves on the CSIDH},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={CSIDH;isogenies;post-quantum;cryptanalysis;hidden-shift problem;Kuperberg's algorithm},
  volume={12105},
  doi={10.1007/978-3-030-45724-2_16},
  author={Chris Peikert},
  year=2020
}