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.