## 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).

### MSC:

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

Zbl 0592.00028