Paper 2018/537

Quantum Security Analysis of CSIDH and Ordinary Isogeny-based Schemes

Xavier Bonnetain and André Schrottenloher

Abstract

CSIDH is a recent proposal by Castryck, Lange, Martindale, Panny and Renes for post-quantum non-interactive key-exchange, to be presented at ASIACRYPT~2018. It is similar in design to a scheme by Couveignes, Rostovtsev and Stolbunov, but it replaces ordinary elliptic curves by supersingular elliptic curves, in order to make significant gains in time and key lengths. Isogeny-based key-exchange on ordinary elliptic curves can be targeted by a quantum subexponential hidden shift algorithm found by Childs, Jao and Soukharev. Although CSIDH uses supersingular curves, it is analog to the case of ordinary curves, hence this algorithm applies. In the proposal, the authors suggest a choice of parameters that should ensure security against this. In this paper, we reassess these security parameters. Our result relies on two steps: first, we propose a new quantum algorithm for the hidden shift problem and analyze precisely its complexity. This reduces the number of group actions to compute w.r.t the authors' estimation; second, we show how to compute efficiently this group action. For example, we show that only $2^{35}$ quantum equivalents of a key-exchange are sufficient to break the 128-bit classical, 64-bit quantum security parameters proposed, instead of $2^{62}$. Finally, we extend our analysis to ordinary isogeny computations, and show that an instance proposed by De Feo, Kieffer and Smith (also accepted at ASIACRYPT 2018) and expected to offer $56$ bits of quantum security can be attacked in $2^{38}$ quantum evaluations of a key exchange.

Note: Updated the quantum algorithm, corrected typos.