[Theory] TODAY 4pm Ramanujan graphs and cryptography

Theory Group Announcements theory at mailman.cs.uchicago.edu
Fri Sep 28 12:57:32 CDT 2007

Today at 4pm there will be a math colloquium
in Eckhart 206.

Title: Applications of Ramanujan graphs in Cryptography.
Kristin Lauter, Microsoft Research

I append the math dept announcement which includes the
          -- Laci


The Association for Women in Mathematics and the Department of Mathematics
inaugurate their joint Colloquium series Friday September 28th at 4PM in
E206. The speaker will be Kristin Lauter from Microsoft Research. 
Refreshments will be provided before the talk in the tea room.
All are invited. The title and abstract are below.

Title: Applications of Ramanujan graphs in Cryptography.

Kristin Lauter, Microsoft Research

Abstract: This talk will explain a new construction of secure cryptographic
hash functions from Ramanujan graphs.  First we will explain cryptographic hash
functions and the importance of the collision-resistance property. After a
brief overview of expander graphs, we will give a construction of provable
collision resistant hash functions from expander graphs in which finding cycles
is hard.

As examples, we give two specific families of optimal expander graphs for
provable collision resistant hash function constructions: the families of
Ramanujan graphs constructed by Lubotzky-Phillips-Sarnak and Pizer
respectively. Pizer described a family of Ramanujan graphs, where the nodes of
the graph are isomorphism classes of supersingular elliptic curves over
$\mathbb{F}_{p^2}$, and the edges are n-isogenies, n a prime different from p.

When the hash function is constructed from one of Pizer's Ramanujan graphs,
then collision resistance follows from hardness of computing isogenies between
supersingular elliptic curves. For the LPS graphs, the underlying hard problem
is a representation problem in group theory.

Joint work with Denis Charles and Eyal Goren

More information about the Theory mailing list