Better Bounds for Finding Fixed-Degree Isogenies via Coppersmith's Method
Marius A. Aardal, Diego F. Aranha, Yansong Feng, Yiming Gao, Yanbin Pan
摘要
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.
问 Lune
几分钟看清这篇 Paper 的位置,不用再花一下午。
Lune 能读引用它和与它最相关的顶会 Paper,讲清它说了什么、后来怎样、哪里站不住,每一点都注明出自哪篇 Paper。不用硬啃,也不靠猜。
相关 Paper
- Improved Algorithms for Finding Fixed-Degree Isogenies Between Supersingular Elliptic CurvesBenjamin Bencina, Péter Kutas, Simon-Philipp Merz, Christophe Petit 等CRYPTO 2024 · 3 次引用
- Accelerating the Delfs-Galbraith Algorithm with Fast Subfield Root DetectionMaria Corte-Real Santos, Craig Costello, Jia ShiCRYPTO 2022 · 10 次引用
- Rational Isogenies from Irrational EndomorphismsWouter Castryck, Lorenz Panny, Frederik VercauterenEUROCRYPT 2020 · 47 次引用
- Improved Torsion-Point Attacks on SIDH VariantsVictoria de Quehen, Péter Kutas, Chris Leonardi, Chloe Martindale 等CRYPTO 2021 · 4 次引用
- A Direct Key Recovery Attack on SIDHLuciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope 等EUROCRYPT 2023 · 136 次引用
