Chennai Mathematical Institute


Three applications of Spectral gaps/Expander graphs in cryptography
Ramarathnam Venkatesan
Microsoft Research, Redmond and Bangalore.


There are three questions:

1. Does the classic Pollard Rho find discrete log in |G|^{0.5} time on an abelian group G?

2. Do all elliptic curves of the same order have the same difficulty of discrete log?

3. How to build a stream cipher that is word based rather than byte based like the ubiquitous RC4?

I outline some answers to these questions, all involving spectral gaps. Item 2 uses the Extended Riemann Hypothesis.

Joint works with Stephen Miller (Rutgers) (1) and (2) and (3), David Jao (Waterloo) (2), Ilya Mironov (Microsoft) (3), Natan Keller (Hebrew) (3).

Search WWW Search