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

---

Abstract

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).