This public lecture was part of the Foundations and Applications of Lattice-based Cryptography workshop at ICMS.
We were delighted to welcome speaker Luca De Feo to give this talk.
Alice and the White Rabbit have a secret rendezvous at 10th Ave. with 20th St. From her spot in Central Park, Alice hikes 56 blocks South and 5 blocks West, while the Rabbit goes 38 blocks South and 5 blocks West. Will the Hatter be able to find their secret hideout and sneak up on them?
Unfortunately, yes. Our Manhattan is not meant for secrets. But in Wonderland there exist multi-dimensional Manhattans where even the maddest hatter could not guess Alice's route of 3 blocks South, 4 West, 5 Azimuth, 7 Qing, 1 Al Gharb, ....
When mathematicians lose all sense of space and distance, they model "reality" with graphs. Expander graphs are like extremely well connected Manhattans, where in just a handful blocks one could find themself at any intersection! But how to find one's way in such a labyrinth?
Expander graphs have long been studied by mathematicians and computer scientist alike. Their elegant structure lends itself to beautiful analyses, and their properties lead to powerful applications. Although random graphs tend to be expanders, optimal expander graphs are difficult to build mathematically, and only a handful of constructions are known. One of the most fascinating is based on Hecke operators acting on spaces of modular forms, a construction that also has interpretations in maximal orders of quaternion algebras and in supersingular elliptic curves over finite fields.
Going in depth about these beautiful connections would take us too far, and probably a PhD or two. But in this presentation we will at least peer under the graph and learn how the mathematical structure not only gives us optimal expanders, but also a compass to find our way in Manhattan, Wonderland. And, lo and behold, this compass will let us do cryptography: hiding messages in gigantic expander graphs that only the intended recipient will be able to find!
Cover image credit: Lorenz Panny