Lune

EUROCRYPT2026顶会

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 dd between supersingular elliptic curves is a fundamental assumption in isogeny-based cryptography. Let E1E_1 and E2E_2 be supersingular elliptic curves defined over Fp2\mathbb{F}_{p^2}, and let dd be a smooth integer. %removed > p^1/2 part. At CRYPTO 2024, Benčina et al. proposed an algorithm with time complexity O~(max⁡{p1/2,d/p5/8})\widetilde{O}(\max\{p^{1/2}, d/p^{5/8}\}) in the classical setting and O~(max⁡{p1/4,d1/2/p1/4})\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/4p))\exp(O(\log^{3/4} p)). We then improve their result to O~(max⁡{p1/2,exp⁡(O(log⁡4/5p))⋅d/p2/3})\widetilde{O}(\max\{p^{1/2}, \exp(O(\log^{4/5} p)) \cdot d/p^{2/3}\}) classically and O~(max⁡{p1/4,exp⁡(O(log⁡4/5p))⋅d1/2/p1/3})\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 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。不用硬啃,也不靠猜。

可以从这些问题问起

Lune 可以查阅

摘要 · 相关的 Paper

获取答案

免费开始,无需绑卡

相关 Paper

  1. Improved Algorithms for Finding Fixed-Degree Isogenies Between Supersingular Elliptic CurvesBenjamin Bencina, Péter Kutas, Simon-Philipp Merz, Christophe Petit 等CRYPTO 2024 · 3 次引用
  2. Accelerating the Delfs-Galbraith Algorithm with Fast Subfield Root DetectionMaria Corte-Real Santos, Craig Costello, Jia ShiCRYPTO 2022 · 10 次引用
  3. Rational Isogenies from Irrational EndomorphismsWouter Castryck, Lorenz Panny, Frederik VercauterenEUROCRYPT 2020 · 47 次引用
  4. Improved Torsion-Point Attacks on SIDH VariantsVictoria de Quehen, Péter Kutas, Chris Leonardi, Chloe Martindale 等CRYPTO 2021 · 4 次引用
  5. A Direct Key Recovery Attack on SIDHLuciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope 等EUROCRYPT 2023 · 136 次引用
黄昏的海面,两侧是细线勾勒的悬崖