Motivated by the recent applications of isogeny graphs in cryptography, we review topics related to isogenies of elliptic curves defined over finite fields, and their computations.
Isogeny graphs come in two families: complex multiplication (CM) and supersingular. CM graphs enjoy a rich structure, related to the theory of the orders of an imaginary quadratic field. We explain how this theory yields practical algorithms to move « vertically » in the graphs, along the lattice of quadratic orders.
However, « practical » does not imply « easy ». In order to efficiently implement our algorithms, we shall review the available methods to compute in the algebraic closure of a finite field. Interestingly, isogenies will also turn out to be useful for these algorithms, their computation thus becoming both a goal and a tool.
Finally, we will review the application of isogeny graphs to cryptographic key exchange. CM graphs will offer a natural generalization of the classical Diffie–Hellman key exchange, a fact already recognized twenty years ago, and recently revamped. The structure of supersingular graphs, on the other hand, is related to the maximal orders of a quaternion algebra, and is harder to handle algorithmically; only recently these graphs have been proposed as a foundation for cryptography.
In both cases, the security of the cryptographic protocols is based on the difficulty of moving « horizontally » in the isogeny graphs. We shall thus conclude our study with a review of the known algorithms, both classical and quantum, to solve these problems.