Cryptographic applications involving Spectral gap

Ramarathnam Venkatesan
Microsoft Research
Cryptography and Anti-Piracy Research Group

I will survey a number of applications that involve rapid mixing at some level:stream ciphers, bit security Curve Diffie-Hellman bits and random reducibility of discrete log on Elliptic curve (assuming GRH), analysis of Pollard Rho, and several constructions of secure hash functions. Each of this applications involve directed graphs and disparate mathematical analysis in a case by case basis. I will also mention some mathematical difficulties that arise in practically meaningful connections to theory.

Back to Expanders in Pure and Applied Mathematics