Welcome to the resource topic for 2023/1618
Title:
Improved algorithms for finding fixed-degree isogenies between supersingular elliptic curves
Authors: Benjamin Benčina, Péter Kutas, Simon-Philipp Merz, Christophe Petit, Miha Stopar, Charlotte Weitkämper
Abstract:Finding isogenies between supersingular elliptic curves is a natural algorithmic problem which is known to be equivalent to computing the curves’ endomorphism rings.
When the isogeny is additionally required to have a specific degree d, the problem appears to be somewhat different in nature, yet it is also considered a hard problem in isogeny-based cryptography.
Let E_1,E_2 be supersingular elliptic curves over \mathbb{F}_{p^2}. We present improved classical and quantum algorithms that compute an isogeny of degree d between E_1 and E_2 if it exists. Let the sought-after degree be d = p^{1/2+ \epsilon} for some \epsilon>0.
Our essentially memory-free algorithms have better time complexity than meet-in-the-middle algorithms, which require exponential memory storage, in the range 1/2\leq\epsilon\leq 3/4 on a classical computer and quantum improvements in the range 0<\epsilon<5/2.
ePrint: https://eprint.iacr.org/2023/1618
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .