The supersingular isogeny path and endomorphism ring problems are\n equivalent

2021/11/02 by Benjamin Wesolowski, Wesolowski, Benjamin · 1 citation
Computer Science · Mathematics · #Cryptography and Residue Arithmetic #Coding theory and cryptography #Algebraic Geometry and Number Theory

paper · pdf · doi:10.48550/arxiv.2111.01481

Abstract

We prove that the path-finding problem in \ℓ-isogeny graphs and the\nendomorphism ring problem for supersingular elliptic curves are equivalent\nunder reductions of polynomial expected time, assuming the generalised Riemann\nhypothesis. The presumed hardness of these problems is foundational for\nisogeny-based cryptography. As an essential tool, we develop a rigorous\nalgorithm for the quaternion analog of the path-finding problem, building upon\nthe heuristic method of Kohel, Lauter, Petit and Tignol. This problem, and its\n(previously heuristic) resolution, are both a powerful cryptanalytic tool and a\nbuilding-block for cryptosystems.\n

Cited by

• Refined Humbert Invariants in Supersingular Isogeny Degree Analysis

Related

• Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs
• The supersingular Endomorphism Ring and One Endomorphism problems are equivalent
• Orienteering with one endomorphism
• Failing to hash into supersingular isogeny graphs
• Unconditional foundations for supersingular isogeny-based cryptography