**On the Hardness of Computing Endomorphism Rings of Supersingular Elliptic Curves**

*Kirsten Eisentraeger and Sean Hallgren and Travis Morrison*

**Abstract: **Cryptosystems based on supersingular isogenies have been
proposed recently for use in post-quantum cryptography. Three problems have
emerged related to their hardness: computing an isogeny between two
curves, computing the endomorphism ring of a curve, and computing
a maximal order associated to it. While some of these problems
are believed to be polynomial-time equivalent based on heuristics,
their relationship is still unknown. We give the first reduction
between these problems, with the aid of one more problem which we
call Action-on-$\ell$-Torsion. We show that computing $\ell$-power
isogenies reduces to computing maximal orders and
Action-on-$\ell$-Torsion.

We also define the notion of a compact representation of an endomorphism, and use this to show that endomorphism rings always have polynomial representation size. We then reduce the endomorphism ring problem to computing maximal orders and Action-on-$\ell$-Torsion, thus laying the foundation for analysis of the hardness of endomorphism ring computation. This identifies these last two problems as one possible way to attack some systems, such as hash functions based on the $\ell$-isogeny graph of supersingular elliptic curves. This gives the potential to use algebraic tools in quaternion algebras to solve the problems. We also discuss how these reductions apply to attacks on a hash function of Charles, Goren, and Lauter.

**Category / Keywords: **Supersingular isogeny based cryptography, number theory

**Date: **received 6 Oct 2017

**Contact author: **txm950 at psu edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20171009:150346 (All versions of this report)

**Short URL: **ia.cr/2017/986

[ Cryptology ePrint archive ]