How to construct CSIDH on Edwards curves (Q6063264)

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.