A note on the security of CSIDH

DOI10.1007/978-3-030-05378-9_9MaRDI QIDQ1738052zbMATH OpenOpenAlexFDO

Authors Jean-François Biasse, Annamaria Iezzi, Michael J. Jacobson jun.

Publication date 29 March 2019

Full work available at URL https://arxiv.org/abs/1806.03656

Mathematics Subject Classification ID

Applications to coding theory and cryptography of arithmetic geometry (14G50) Theta functions and curves; Schottky problem (14H42) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Abstract: We propose an algorithm for computing an isogeny between two elliptic curves $E_1,E_2$ defined over a finite field such that there is an imaginary quadratic order $mathcalO$ satisfying $mathcalOsimeqoperatornameEnd(E_i)$ for $i=1,2$. This concerns ordinary curves and supersingular curves defined over $mathbb{F}_p$ (the latter used in the recent CSIDH proposal). Our algorithm has heuristic asymptotic run time $e^{Oleft(sqrtlog(|Delta|)ight)}$ and requires polynomial quantum memory and $e^{Oleft(sqrtlog(|Delta|)ight)}$ classical memory, where $Delta$ is the discriminant of $mathcalO$. This asymptotic complexity outperforms all other available method for computing isogenies. We also show that a variant of our method has asymptotic run time $e^{ildeOleft(sqrtlog(|Delta|)ight)}$ while requesting only polynomial memory (both quantum and classical).

Recommendations

• Quantum security analysis of CSIDH
• Constructing elliptic curve isogenies in quantum subexponential time
• A quantum algorithm for computing isogenies between supersingular elliptic curves
• A trade-off between classical and quantum circuit size for an attack against CSIDH
• Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies

Cited in

(21)

• On the hardness of the computational ring-LWR problem and its applications
• CSIDH: an efficient post-quantum commutative group action
• A trade-off between classical and quantum circuit size for an attack against CSIDH
• Threshold schemes from isogeny assumptions
• He gives C-sieves on the CSIDH
• Quantum security analysis of CSIDH
• Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE
• New techniques for SIDH-based NIKE
• A subexponential-time, polynomial quantum space algorithm for inverting the CM group action
• Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies
• Cryptographic group actions and applications
• A quantum algorithm for computing isogenies between supersingular elliptic curves
• scientific article; zbMATH DE number 2009974 (Why is no real title available?)
• The supersingular isogeny problem in genus 2 and beyond
• Constructing elliptic curve isogenies in quantum subexponential time
• Orienteering with one endomorphism
• Explicit Isogenies of Prime Degree Over Quadratic Fields
• DeCSIDH: delegating isogeny computations in the CSIDH setting
• PQC CSIKE algorithm on non-cyclic Edwards curves
• CSI-Otter: isogeny-based (partially) blind signatures from the class group action with a twist
• Supersingular non-superspecial abelian surfaces in cryptography

This page was built for publication: A note on the security of CSIDH

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1738052)