•Because the random walk converges quickly,
expander graphs make for excellent random number generators.

–They can convert “bad
generators” into better ones

–Rivest’s RC4 is based on
expanders on permutation groups

•When the nodes represent
different instances of the same problem, the random walk can sometimes be used
to show that each instance is as “difficult” as the rest.

•Such “self-reducibility”
is important in cryptography, because one wants all versions of
a given system to be hard to break.

•Recent application (Jao,
Miller, Venkatesan): ensuring security of Microsoft’s next *product key* (a 25 digit alpha-numeric
code one enters when installing Windows or Office).

Cryptographic
Applications