Next: Construction of hard-core predicates Up: Further results on pseudo-random Previous: Further results on pseudo-random

## Hard-Core Predicates and Pseudo-Random Numbers

We have seen several functions with the property that was easy to compute but was difficult. Such an is called a one-way function.16 A predicate is a property which is true or false for any . Typical examples might be is an odd number'' or is .'' A hard-core predicate for a function is a predicate such that
1.
there is an efficient algorithm for deciding whether is true
2.
if we are given , there is no efficient algorithm for guessing whether is true which has a probability much greater than of being right.
The example we used in the quadratic number generator was

where we are looking only at those which are squares.

Theorem 32   If is a hard-core predicate for , the random number generator in which a seed is chosen at random, giving the sequence of bits

satisfies the Next Bit Condition.

As a corollary, the sequence , ,...satisfies all efficient tests, using the arguments in the preceding section.

Proof: If there were a program which took as input a se quence of bits and could guess the next bit, we could get a good guess on with known by asking the next-bit predictor what would occur next in the sequence

(this is really the same proof as in the case of the quadratic generator).

#### Footnotes

... function.16
In later work, we will be defining a one-way function to be such that there is no efficiently computable with for most .

Next: Construction of hard-core predicates Up: Further results on pseudo-random Previous: Further results on pseudo-random
Translated from LaTeX by Scott Sutherland
1998-03-15