Better Bounds for Finding Fixed-Degree Isogenies via Coppersmith's Method

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$ be a smooth integer. %removed > p^1/2 part. 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 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.