International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 01 April 2014

Sorina Ionica, Emmanuel Thomé
ePrint Report ePrint Report
An isogeny graph is a graph whose vertices are principally polarized

abelian varieties and whose edges are isogenies between these varieties. In

his thesis, Kohel described the structure of isogeny graphs for elliptic

curves and showed that one may compute the endomorphism ring of an elliptic

curve defined over a finite field by using a depth first search algorithm

in the graph. In dimension 2, the structure of isogeny graphs is less understood and existing algorithms for computing endomorphism rings are very expensive.

Our setting considers genus 2 jacobians with complex multiplication,

with the assumptions that the real multiplication subring is maximal and

has class number one. We fully describe the isogeny graphs in that

case.

Over finite fields, we derive a depth first search algorithm for computing endomorphism rings locally at prime numbers, if the real multiplication is maximal. To the best of our knowledge, this is the first DFS-based algorithm in genus 2.

Expand

Additional news items may be found on the IACR news page.