Better Bounds for Finding Fixed-Degree Isogenies via Coppersmith's Method
Marius A. Aardal, Diego F. Aranha, Yansong Feng, Yiming Gao, Yanbin Pan
Abstract
The hardness of finding isogenies of degree between supersingular elliptic curves is a fundamental assumption in isogeny-based cryptography. Let and be supersingular elliptic curves defined over , and let be a smooth integer. %removed > p^1/2 part. At CRYPTO 2024, Benčina et al. proposed an algorithm with time complexity in the classical setting and in the quantum setting.
In this work, we first observe that their analysis omits a sub-exponential factor . We then improve their result to classically and 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 the SIDH signature scheme by Basso et al. (ACNS 2024). We expect that these refined techniques for Coppersmith’s method will be valuable for further post-quantum cryptanalysis.
Ask Lune
Know where this paper stands in minutes, not an afternoon.
Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Improved Algorithms for Finding Fixed-Degree Isogenies Between Supersingular Elliptic CurvesBenjamin Bencina, Péter Kutas, Simon-Philipp Merz, Christophe Petit et al.CRYPTO 2024 · 3 citations
- Accelerating the Delfs-Galbraith Algorithm with Fast Subfield Root DetectionMaria Corte-Real Santos, Craig Costello, Jia ShiCRYPTO 2022 · 10 citations
- Rational Isogenies from Irrational EndomorphismsWouter Castryck, Lorenz Panny, Frederik VercauterenEUROCRYPT 2020 · 47 citations
- Improved Torsion-Point Attacks on SIDH VariantsVictoria de Quehen, Péter Kutas, Chris Leonardi, Chloe Martindale et al.CRYPTO 2021 · 4 citations
- A Direct Key Recovery Attack on SIDHLuciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope et al.EUROCRYPT 2023 · 136 citations
