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

“The hardness of finding isogenies of a given degree between supersingular elliptic curves is a core assumption in isogeny-based cryptography. For curves defined over a quadratic extension of a finite field and a smooth degree, prior work by Danilo Benčina et al. at CRYPTO 2024 gave classical and quantum algorithms with running times governed by tradeoffs between the field size and the degree. We show that their analysis misses a subexponential factor and refine the bounds, improving the dependence on the degree in both the classical and quantum settings up to a mild subexponential term. Our method uses small-root bounds from Don Coppersmith’s technique on a four-variable integer equation, adapting recent results from CRYPTO 2025 to the integer setting. As an application, we strengthen their attack on the SIDH-based signature scheme of Andrea Basso et al. (ACNS 2024).”