Cryptology ePrint Archive: Report 2021/372

Explicit connections between supersingular isogeny graphs and Bruhat–Tits trees

Laia Amorós and Annamaria Iezzi and Kristin Lauter and Chloe Martindale and Jana Sotáková

Abstract: We give an exposition of supersingular isogeny graphs, quaternion ideal graphs and Bruhat–Tits trees, and of their connections. Bruhat–Tits trees are combinatorial objects whose vertices and edges have a very simple representation as two-by-two matrices, which, as we show, is useful for understanding certain aspects of the corresponding elliptic curves and isogenies. Moreover Bruhat–Tits trees can be given an orientation and a notion of depth that we translate into the setting of supersingular isogeny graphs. We give some suggestions towards using Bruhat–Tits trees as a tool for cryptanalysis of certain cryptosystems based on supersingular isogeny graphs.

Category / Keywords: public-key cryptography / isogeny, SIKE, SIDH, quaternions, Bruhat-Tits, elliptic curves

Original Publication (with minor differences): Women in Numbers Europe III: Research Directions in Number Theory.

Date: received 19 Mar 2021

Contact author: laia ac at protonmail com, annamaria iezzi@gmail com, kristinelauter@gmail com, chloe martindale@bristol ac uk, ja sotakova@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210322:193318 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]