CSIDH: An efficient post-quantum commutative group action

There are five attempts at assessing the security of CSIDH: A first one in the paper, three independent ones after we posted a first version of this paper on the Cryptology ePrint Archive, and one by a subset of the CSIDH authors together with Bernstein. For details see below.

Biasse, Iezzi, and Jacobson

Biasse, Iezzi, and Jacobson work out some more details of the attack ideas for applying Regev's algorithm. They focus on the class-group-computation part of the oracle and they work out how to represent random elements of the class group as a product of small prime ideals. Their analysis is purely asymptotic and an assessment of the actual cost on specific instances is explicitly left for future work.

Bonnetain and Schrottenloher

Bonnetain and Schrottenloher determine (quantum) query complexities for breaking CSIDH under the assumption that the quantum memory can be made very large, which implies that Kuperberg's faster algorithms would be applicable. They estimate the number of oracle queries as (5π2/4) 21.8√ log N . The 1.8 appears to approximate the √ 2 log 3  in Theorem 5.1 in Kuperberg. They state 22.3+ 1.8√ log N  for the number of qubits.

While we ignored Kuperberg's algorithm due to the large memory costs, they take the stance that "the most time-efficient version is relevant", and so do not ignore this algorithm. For small N the number of qubits stated by Bonnetain and Schrottenloher might be possible, which would indeed make Kuperberg's algorithm relevant for these sizes. However, in this case the total cost is dominated by the high cost of computing the oracle, which Childs–Jao–Soukharev placed at Lp [1/2,1/√ 2 ]. Bonnetain and Schrottenloher instead make use of Couveignes' (exponential-time, but perhaps better for small parameters) LLL-based method for the oracle computation, but apply BKZ for more effective lattice-basis reduction.

The current version of Bonnetain–Schrottenloher also presents concrete estimates for the attack costs for our parameter sets, but unfortunately this version ignores most of the cost of evaluating isogenies. For example: 1. The algorithm to evaluate isogenies in our paper makes heavy use of input-dependent branches, which is impossible in superposition; 2. Bonnetain and Schrottenloher skip finding points of order li which are needed as the kernel of the li-isogeny; 3. Bonnetain and Schrottenloher apply a result for multiplication costs in F2n to multiplications in Fp. We analyzed the (significantly higher) cost of a quantum oracle for isogeny evaluation and conclude that the current estimates of Bonnetain–Schrottenloher do not imply that CSIDH-512 is broken under NIST level 1 (see below for more details and a reference).

Jao, LeGrow, Leonardi, and Ruiz-Lopez

Jao, LeGrow, Leonardi, and Ruiz-Lopez recently made a preprint of their MathCrypt paper available to us. They address the issue of superpolynomial space in the oracle computation identified by Galbraith and Vercauteren (stated above) and give a new algorithm for finding short representations of elements. Their paper focuses on the asymptotic analysis of the oracle step so that they achieve overall polynomial quantum space, but does not obtain any concrete cost estimates.

Bernstein, Lange, Martindale, and Panny

Bernstein, Lange, Martindale, and Panny analyze the cost of quantum evaluation of isogenies. In Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies they introduce several speedups to arithmetic in finite fields and computing isogenies in superposition, yet for CSIDH-512 they require 240 quantum operations on a quantum computer of 240 qubits to compute a single evaluation of the Kuperberg or Regev oracle for success probability 2-32 and reduced range of exponents. They also give a more detailed analysis of the shortcomings and errors in Bonnetain-Schrottenloher.


Version: This is version 2018.11.18 of the "Analysis" web page.