Supersingular Curves With Small Non-integer Endomorphisms
This addresses a challenge in isogeny-based cryptography for researchers, providing an efficient method for computing isogenies between specific curves that are not easily connected through existing graph-search techniques, though it appears incremental as it focuses on a special class of curves.
The paper tackles the problem of computing isogenies between supersingular curves that lack small-degree connections in standard graphs by introducing a class of curves with small non-integer endomorphisms, showing that isogenies between these curves can be computed efficiently despite partitioning into subsets with no small-degree isogenies between them.
We introduce a special class of supersingular curves over $\mathbb{F}_{p^2}$, characterized by the existence of non-integer endomorphisms of small degree. A number of properties of this set is proved. Most notably, we show that when this set partitions into subsets in such a way that curves within each subset have small-degree isogenies between them, but curves in distinct subsets have no small-degree isogenies between them. Despite this, we show that isogenies between these curves can be computed efficiently, giving a technique for computing isogenies between certain prescribed curves that cannot be reasonably connected by searching on $\ell$-isogeny graphs.