Welcome to the resource topic for 2025/1812
Title:
Better Bounds for Finding Fixed-Degree Isogenies via Coppersmith’s Method
Authors: Marius A. Aardal, Diego F. Aranha, Yansong Feng, Yiming Gao, Yanbin Pan
Abstract:The hardness of finding isogenies of degree d between supersingular elliptic curves is a fundamental assumption in isogeny-based cryptography. Let E_1 and E_2 be supersingular elliptic curves defined over \mathbb{F}_{p^2}, and let d>p^{1/2} be smooth. At CRYPTO~2024, Benčina et al.\ proposed an algorithm with time complexity \widetilde{O}(\max\{p^{1/2}, d/p^{5/8}\}) in the classical setting and \widetilde{O}(\max\{p^{1/4}, d^{1/2}/p^{1/4}\}) in the quantum setting.
In this work, we first observe that their analysis omits a sub-exponential factor \exp(O(\log^{3/4} p)). We then improve their result to \widetilde{O}(\max\{p^{1/2},\exp(O(\log^{4/5} p)) \cdot d/p^{2/3}\}) classically and \widetilde{O}(\max\{p^{1/4}, \exp(O(\log^{4/5} p)) \cdot d^{1/2}/p^{1/3}\}) quantumly. Our approach relies on small-root bounds for Coppersmith’s method applied to a four-variable integer equation. To this end, we adapt the explicit asymptotic formulas for small-root bounds introduced by Feng et al.\ (CRYPTO~2025) in the modular setting to the integer setting. As an additional application, we strengthen the attack of Benčina et al.\ on a signature scheme introduced at ACNS~2024, reducing its security by 9 bits. We expect that these refined techniques for Coppersmith’s method will be valuable for further post-quantum cryptanalysis.
ePrint: https://eprint.iacr.org/2025/1812
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 .