Quantum Security Analysis of CSIDH and Ordinary Isogeny-based Schemes

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/hal-01896046
Contributor : André Schrottenloher <>
Submitted on : Monday, October 15, 2018 - 5:25:02 PM
Last modification on : Friday, April 19, 2019 - 4:55:25 PM
Long-term archiving on: Wednesday, January 16, 2019 - 3:42:59 PM

File

2018-537.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01896046, version 1

Collections

Citation

Xavier Bonnetain, André Schrottenloher. Quantum Security Analysis of CSIDH and Ordinary Isogeny-based Schemes. 2018. ⟨hal-01896046⟩

Share

Metrics

Record views

89

Files downloads

108