Supersingular curves you can trust

 

Dr. Travis Morrision, Virginia Tech
Thursday, December 7 – 11 :00AM
Location: 016 Manchester Hall

A useful feature of elliptic curve cryptography is the ability to “hash into” the set of points on an elliptic curve: a user can easily compute a uniformly random point on the curve in a way so that no one (not even the user!) knows the discrete logarithm of that point relative to the public base point. It is not known whether isogeny-based cryptography enjoys this functionality. In isogeny-based cryptosystems, a private key is an isogeny from a fixed public supersingular elliptic curve, and the corresponding public key is the codomain of that isogeny, another supersingular elliptic curve. Public keys can be thought of as vertices in the supersingular isogeny graph, and private keys are random walks (beginning at the fixed public curve) in that graph. Whether one can “hash into” the supersingular isogeny graph is an open question: there is no known method for quickly computing a random supersingular elliptic curve that does not also provide, as a byproduct, the ring of endomorphisms of the supersingular elliptic curve. With knowledge of the endomorphism ring, one can easily find a path back to the public base curve. There are isogeny-based cryptosystems that can only be securely instantiated given a single supersingular elliptic curve with unknown endomorphism ring – a supersingular curve you can trust. In this talk, I will discuss a practical, distributed protocol for computing a supersingular elliptic curve with unknown endomorphism ring and the first statistically zero knowledge proof of knowledge of a secret isogeny. This is based on joint work with Basso, Codogni, Connolly, De Feo, Fouotsa, Lido, Panny, Patranabis, and Wesolowski.