Paper 2024/1971 Original: eprint.iacr.org/2024/1971 ↗

Further Connections Between Isogenies of Supersingular Curves and Bruhat-Tits Trees

Abstract

We further explore the explicit connections between supersingular curve isogenies and Bruhat-Tits trees. By identifying a supersingular elliptic curve $E$ over $\mathbb{F}_p$ as the root of the tree, and a basis for the Tate module $T_\ell(E)$; our main result is that given a vertex $M$ of the Bruhat-Tits tree one can write down a generator of the ideal $I \subseteq \text{End}(E)$ directly, using simple linear algebra, that defines an isogeny corresponding to the path in the Bruhat-Tits tree from the root to the vertex $M$. In contrast to previous methods to go from a vertex in the Bruhat-Tits tree to an ideal, once a basis for the Tate module is set up and an explicit map $\Phi : \text{End}(E) \otimes_{\mathbb{Z}_\ell} \to M_2( \mathbb{Z}_\ell )$ is constructed, our method does not require any computations involving elliptic curves, isogenies, or discrete logs. This idea leads to simplifications and potential speedups to algorithms for converting between isogenies and ideals.