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. 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 show that those security parameters were too optimistic. Our result relies on two steps: first, we give a more precise complexity analysis of the hidden shift algorithm in this context, which greatly reduces the number of group actions to compute; 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}$. When compared against levels of security defined in the NIST post-quantum call, the parameters proposed need to be increased in order to reach the target levels: at the AES-128 security level, a base field of at least $1024$ bits is necessary, instead of $512$ bits (i.e public key sizes of $128$ bytes). Finally, we extend our analysis to ordinary isogeny computations, and show that an instance proposed by De Feo, Kieffer and Smith and expected to offer $56$ bits of quantum security can be broken in $2^{38}$ quantum evaluations of a key exchange.

Note: Updated the quantum algorithm, corrected typos.