Choosing safe post-quantum parameters for the new CSIDH isogeny-based key-exchange system requires concrete analysis of the cost of quantum attacks. The two main contributions to attack cost are the number of queries in hidden-shift algorithms and the cost of each query.

The cost of each query includes the cost of evaluating a group action, a series of isogenies, in superposition. This page reports on our results of analyzing and optimizing this cost. Each quantum attack incurs this cost many times.

Our main result has the following shape: the CSIDH group action can be carried out in B nonlinear bit operations (counting ANDs and ORs, allowing free XORs and NOTs) with failure probability at most ε. (All of our algorithms know when they have failed.) This implies a reversible computation of the CSIDH group action with failure probability at most ε using at most 2B Toffoli gates (allowing free NOTs and CNOTs). This in turn implies a quantum computation of the CSIDH group action with failure probability at most ε using at most 14B T-gates (allowing free Clifford gates).

The paper below explains how to compute pairs (B,ε) for any given CSIDH parameters. For example, we show how to compute CSIDH-512 for uniform random exponent vectors in {-5,...,5}^74 using

• 1118827416420 = 2^40 nonlinear bit operations using the algorithm of Section 7, or

• 765325228976 = 0.7 2^40 nonlinear bit operations using the algorithm of Section 8,

in both cases with failure probability below 2^-32. CSIDH-512 is the smallest parameter set considered for CSIDH. For comparison, computing the same action with failure probability 2^-32 using the Jao–LeGrow–Leonardi–Ruiz-Lopez algorithm, with the underlying modular multiplications computed by the same algorithm as in Roetteler–Naehrig–Svore–Lauter, would use approximately 2^51 nonlinear bit operations.

We exploit a variety of algorithmic ideas, including several new ideas pushing beyond the previous state of the art in isogeny computation, with the goal of obtaining the best pairs (B,ε). We introduce a new constant-time variable-degree isogeny algorithm, a new application of the Elligator map, new ways to handle failures in isogeny computations, new combinations of the components of these computations, new speeds for integer multiplication, and more.

Papers

(PDF) Daniel J. Bernstein, Tanja Lange, Chloe Martindale, Lorenz Panny. "Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies." Eurocrypt 2019, to appear. Document ID: 9b88023d7d9ef3f55b11b6f009131c9f. Date: 2019.03.05. Supersedes: (PDF) 2018.10.31.

Funding

This work was supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 643161 (ECRYPT-NET), 645622 (PQCRYPTO), 645421 (ECRYPT-CSA), and CHIST-ERA USEIT (NWO project 651.002.004); the Netherlands Organisation for Scientic Research (NWO) under grants 628.001.028 (FASOR) and 639.073.005; and the U.S. National Science Foundation under grant 1314919. "Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation" (or other funding agencies).