How to construct random functions. (English) Zbl 0596.65002

Theory of algorithms, Colloq. Pécs/Hung. 1984, Colloq. Math. Soc. János Bolyai 44, 161-189 (1986).
Summary: [For the entire collection see Zbl 0592.00028.]
A constructive theory of randomness for functions is developed, based on computational complexity. We present a deterministic polynomial-time algorithm that transforms pairs \((g,r)\), where \(g\) is any one-way (in a very weak sense) function and \(r\) is a random \(k\)-bit string, to polynomial-time computable functions \(f_ r:\{1,...2^ k\}\to \{1,...,2^ k\}\). These \(f_ r\)’s cannot be distinguished from random functions by any probabilistic polynomial time algorithm that asks and receives the value of a function at arguments of its choice.
The journal version has been published in J. Assoc. Comput. Mach. 33, No. 4, 792–807 (1986).


65C10 Random number generation in numerical analysis
68Q25 Analysis of algorithms and problem complexity
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)


Zbl 0592.00028