Group, Lie and Number Theory Seminar

A quantum computer at scale would break all currently deployed cryptography. To prepare for this, the NSA and NIST are both pushing for the standardization of "post-quantum" or "quantum-secure" cryptosystems, meaning cryptographic protocols which would resist attacks deployed by a quantum computer (but can still run on classical computers). Supersingular isogeny problems are one attractive source of hardness assumptions for such cryptosystems. They are also fundamental computational problems in arithmetic geometry, as they involve either computing an isogeny between two given supersingular elliptic curves, or computing their endomorphism rings. These two problems are deeply connected, but it is not clear to what extent they are equivalent. Now that the various competing protocols are being held up to scrutiny, it is important to understand the relative complexity of their computational hardness assumptions. In joint work with K. Eisentraeger and S. Hallgren, we show that the problem of computing an isogeny of prime-power degree between two curves has a polynomial time reduction to a version of the problem of computing endomorphism rings. I will discuss background on supersingular elliptic curves and give an example of how they can be used to build a cryptosystem using their isogeny graphs. Then I will explain the connection between the arithmetic of quaternion algebras and isogenies of supersingular elliptic curves, and how we use this correspondence in our reduction. Speaker(s): Travis Morrison (Pennsylvania State University)