Back to the root file of my research overview.

Pseudorandomness and Foundations of Cryptography

While our scientific culture holds sacred the distinction between deterministic and random processes, it seems now to be an easily created illusion closely related to another fundamental mystery of Computer Science: one-way functions (OWF). Pseudo-random generators (PRG) are among basic tools in many areas of computer theory and practice. Most are purely empirical, but the perfect faithfulness of some was evidenced in [Blum, Micali], [Yao], based on conjectures that certain functions are one-way, i.e., easy to compute while infeasible to invert. Many candidates are believed but none proven to be OWF. [Levin 87], [Goldreich, Levin], [Hastad, Impagliazzo, Levin, Luby], [Levin 93] clarified the connection between PRG and OWF, removed the dependence on the specific functions being OWF and eliminated the security loss. Look at https://www.cs.bu.edu/fac/lnd/expo/icm94.htm for a non-technical description of these results. A nice technical exposition accessible to non-experts can be found in [Knuth].

The efficient version of these and other applications require strong OWF, i.e., those hard to invert on all but a negligible fraction of instances. They can be readily obtained from any weak OWF, i.e. one hard to invert on a polynomial fraction of instances (or on average, if the concept is defined carefully). Almost all security is, however, lost in the straightforward transformation, even for permutations. In our FOCS-90 paper, the use of random walks on constructive expanders allowed to preserve security (running-time of inverting algorithms). Like my FOCS-88 paper, this is one of the first applications of constructive expanders to the general theory of computation.