zbMATH — the first resource for mathematics

On the existence of pseudorandom generators. (English) Zbl 0717.65001
Advances in cryptology - Crypto ’88, Proc. Conf., Santa Barbara, CA/USA 1988, Lect. Not. Comput. Sci. 403, 146-162 (1990).
[For the entire collection see Zbl 0709.00023.]
Pseudorandom generators are programs that transform a random k-bit seed into a much longer sequence of bits. This generated sequence should be indistinguishable in polynomial time from a random sequence of bits.
The paper deals with the problem of existence of pseudorandom generators. The notion of ‘one-way function’ is used. Roughly speaking, a function is one-way if it cannot be efficiently inverted by means of any probabilistic polynomial time algorithm. The authors introduce the notion of ‘regular function’. A function is ‘regular’ if every image of k-bit string has the same number of preimages of length k.
The main theorem proved in the paper is that there exist pseudorandom generators based on regular one-way functions. Some extensions of this theorem are investigated. Several examples of generators are given.
Reviewer: P.Staniewski

65C10 Random number generation in numerical analysis