[Resource Topic] 2017/986: On the Hardness of Computing Endomorphism Rings of Supersingular Elliptic Curves

Welcome to the resource topic for 2017/986

On the Hardness of Computing Endomorphism Rings of Supersingular Elliptic Curves

Authors: Kirsten Eisentraeger, Sean Hallgren, Travis Morrison


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.

ePrint: https://eprint.iacr.org/2017/986

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .