Computing the endomorphism ring of a supersingular elliptic curve is the central hard problem in isogeny-based cryptography. In this talk, we will present an algorithm for computing inseparable endomorphisms of a given supersingular elliptic curve. The algorithm requires low storage and is easy to parallelize, and conditional on the Generalized Riemann Hypothesis, terminates in O~(p^(1/2)) bit operations, matching the time complexity of generic algorithms. Unlike generic algorithms, the algorithm produces endomorphisms which generate quadratic orders with predictable discriminants; this allows us to prove arithmetic properties (such as being Gorenstein or Bass) of the quaternionic orders generated by endomorphisms produced by our algorithm. Let P denote the 2-sided ideal of inseparable endomorphisms of a supersingular elliptic curve E in characteristic p. Then our algorithm outputs endomorphisms contained in P. We prove that two calls to our algorithm for computing inseparable endomorphisms produces a generating set for a Bass suborder of the endomorphism ring. I'll discuss a heuristic argument that the expected number of calls required to produce a generating set for Z+P, the unique index p suborder of index p in End(E), is bounded by a constant, independent of p. This is joint work with Fuselier, Iezzi, Kozek, and Namoijam and began at the first Rethinking Number Theory workshop.
Computing supersingular endomorphism rings using inseparable endomorphisms
A useful feature of elliptic curve cryptography is the ability to "hash into" the set of public keys: a user can easily compute a uniformly random public key in a way so that no one (not even the user!) knows the corresponding private key. 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, enough information to easily find a path from that curve to the fixed public base curve. This byproduct is the ring of endomorphisms of the supersingular elliptic curve: there is no known efficient algorithm for computing the endomorphism ring, and computing endomorphism rings is exactly as hard as path-finding in isogeny graphs. 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. The main ingredient in this protocol is another protocol, a proof of knowledge, that proves knowledge of a secret isogeny. We show this proof of knowledge is statistically zero-knowledge (the protocol does not reveal anything other than the fact that the prover knows the secret information). To prove that our proof of knowledge is statistically zero-knowledge, we introduce isogeny graphs with level structure and prove that these graphs are Ramanujan graphs: random walks mix as rapidly as possible. In this talk, I will discuss isogeny-based cryptography at a high level and explain our distributed protocol and proof of knowledge. I will then explain why the Ramanujan-Peterrson conjecture implies that our isogeny graphs with level structure have the Ramanujan property, and hence why our proof of knowledge is statistically zero-knowledge. This is based on joint work with Basso, Codogni, Connolly, De Feo, Fouotsa, Lido, Panny, Patranabis, and Wesolowski.
(NOTE SPECIAL TIME) Supersingular curves you can trust
I first met Walter Taylor in 2018 at the Algebras and Lattices in Hawai'i conference. He presented his result from the previous year that there exist 2-dimensional simplicial complexes which admit the structure of topological modular lattice but not topological distributive lattice. He also asked whether similar examples exist for higher-dimensional simplicial complexes. I will present an n-dimensional analogue of Taylor's book-spaces and show that they are similarly topologically modular-but-not-distributive. There will be pictures.
This talk is for general audience. We will start with some basics definitions and results of finite dimensional Lie algebras. Then we will extend these results to infinite dimensions finding an amazing! relation with the theory of modular forms.
Finally, if time permits, I will mention some modern results relating finite and infinite dimensional algebras with symplectic singularities. These relations are very interesting! "Symplectic singularities are the Lie algebras of the 21st century" (A. Okounkov)
Representation theory of infinite dimensional Lie algebras
Sep. 24, 2024 3:30pm (MATH 3…
Topology
Agnès Beaudry
X
This talk is a continuation of last week's talk. We will discuss the spectrum of the stable homotopy category, introducing the Morava K-theories K(n), the role of v_n self-maps and other central localizations of this category.
Computing supersingular endomorphism rings using inseparable endomorphisms