Paper 2024/1971

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

Valerie Gilchrist, Université Libre de Bruxelles

Shai Levin, University of Auckland

Ari Markowitz, University of Auckland

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.

Note: Updated publication info, and made clear an implicit assumption in Example 1 and Sec. 2.3.

@misc{cryptoeprint:2024/1971,
      author = {Steven Galbraith and Valerie Gilchrist and Shai Levin and Ari Markowitz},
      title = {Further Connections Between Isogenies of Supersingular Curves and Bruhat-Tits Trees},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1971},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1971}
}