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) 2^{1.8√ log N }.
The 1.8 appears to approximate the √ 2 log 3 in
Theorem 5.1 in Kuperberg.
They state 2^{2.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 *L*_{p}
[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 l_{i} which
are needed as the kernel of the l_{i}-isogeny;
3. Bonnetain and Schrottenloher apply a result for multiplication costs in **F**_{2n} to multiplications in **F**_{p}.
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 2^{40}
quantum operations on a quantum computer of 2^{40} 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.