How to construct CSIDH on Edwards curves

DOI10.1016/J.FFA.2023.102310MaRDI QIDQ6063264zbMATH OpenOpenAlexFDO

Authors Tomoki Moriya, Hiroshi Onuki, Tsuyoshi Takagi

Publication date 7 November 2023

Published in Finite Fields and their Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.ffa.2023.102310

zbMATH Keywords

CSIDHEdwards curvesisogeny-based cryptographyMontgomery curvespost-quantum cryptography

Mathematics Subject Classification ID

Applications to coding theory and cryptography of arithmetic geometry (14G50) Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Review text

Isogeny-based cryptography relies on the complexity of the Isogeny Problem, which involves computing isogenies between elliptic curves. This cryptographic branch is a promising candidate for post-quantum cryptography. \textit{D. Jao} and \textit{L. De Feo} [Lect. Notes Comput. Sci. 7071, 19--34 (2011; Zbl 1290.94094)] introduced SIDH (Supersingular Isogeny Diffie-Hellman), a key exchange protocol based on isogenies, later resulting in SIKE (Supersingular Isogeny Key Encapsulation) becoming a 4th round candidate in the NIST post-quantum cryptography standardisation. However, \textit{W. Castryck} and \textit{T. Decru} [Lect. Notes Comput. Sci. 14008, 423--447 (2023; Zbl 1528.94038)] demonstrated a vulnerability in SIDH. Subsequently, \textit{W. Castryck} et al. proposed CSIDH (Commutative Supersingular Isogeny Diffie-Hellman) in [Lect. Notes Comput. Sci. 11274, 395--427 (2018; Zbl 1407.81084)], operating on supersingular elliptic curves over \(\mathbb{F}_p\). CSIDH relies on a commutative group action on \(\mathbb{F}_p\)-isomorphism classes of supersingular Montgomery curves over \(\mathbb{F}_p\), utilising \(\pi_p\), the \(p\)-Frobenius map, to determine the action's points. Their work demonstrates that selecting a random element from \(\mathbb{F}_p\) as an \(x\)-coordinate of a Montgomery curve yields a point in \(\ker(\pi_p -1)\) or \(\ker(\pi_p +1)\), essential for CSIDH's computations. Furthermore, they establish the uniqueness of a Montgomery coefficient up to \(\mathbb{F}_p\)-isomorphism, enabling CSIDH group action computations solely through \(\mathbb{F}_p\)-arithmetic, simplifying operations. \textit{M. Meyer} and \textit{S. Reith} [Lect. Notes Comput. Sci. 11356, 137--152 (2018; Zbl 1407.81087)] introduced a faster CSIDH algorithm using isogenies over Edwards curves instead of Montgomery curves. Edwards curves possess cryptographic significance due to their complete group law on \(E(\mathbb{F}_p)\), enabling efficient addition formulae in certain cases. The paper's focus is on extending the CSIDH algorithm to purely Edwards curves over \(\mathbb{F}_p\). The core of the paper introduces four key results, providing the groundwork for constructing the algorithm to evaluate the class group action based on Edwards curves. These results include a method to compute w-coordinates of points in \(E_d\), ensuring unbiased point generation, demonstrating comparable success probabilities to those on Montgomery curves, and establishing the uniqueness of the \(d\)-coefficient as a shared key. Emphasising the class group action's significance in CSIDH, the authors specifically explore its implications within the realm of Edwards curves, presenting Vélu formulae tailored to this context. To enhance the algorithm's efficiency, an extended Elligator construction for Edwards curves is proposed, enabling cryptographic key exchange using elliptic curves as a form of random noise concealment. Finally, the paper concludes with an in-depth analysis and implementation, complemented by detailed appendices.

Recommendations

• How to construct CSIDH on Edwards curves
• EdSIDH: supersingular isogeny Diffie-Hellman key exchange on Edwards curves
• Optimized method for computing odd-degree isogenies on Edwards curves
• PQC CSIKE algorithm on non-cyclic Edwards curves
• A review of mathematical and computational aspects of CSIDH algorithms

Cites work

• A faster way to the CSIDH
• A method for obtaining digital signatures and public-key cryptosystems
• A normal form for elliptic curves
• A simple and compact algorithm for SIDH with arbitrary degree isogenies
• Abelian varieties over finite fields
• Analogues of Vélu's formulas for isogenies on alternate models of elliptic curves
• Computing isogenies between supersingular elliptic curves over \(\mathbb {F}_p\)
• CSIDH on the surface
• CSIDH: an efficient post-quantum commutative group action
• Differential addition on twisted Edwards curves
• Elliptic Curve Cryptosystems
• Faster Addition and Doubling on Elliptic Curves
• Faster computation of isogenies of large prime degree
• How to construct CSIDH on Edwards curves
• scientific article; zbMATH DE number 3948147 (Why is no real title available?)
• scientific article; zbMATH DE number 3539809 (Why is no real title available?)
• On isogeny classes of Edwards curves over finite fields
• On lions and elligators: an efficient constant-time implementation of CSIDH
• Optimized method for computing odd-degree isogenies on Edwards curves
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Speeding the Pollard and Elliptic Curve Methods of Factorization
• Stronger and faster side-channel protections for CSIDH
• The Arithmetic of Elliptic Curves
• Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies
• Twisted Edwards Curves
• Twisted Edwards Curves Revisited

Cited in

(2)

• PQC CSIKE algorithm on non-cyclic Edwards curves
• A review of mathematical and computational aspects of CSIDH algorithms

This page was built for publication: How to construct CSIDH on Edwards curves

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