Hard-Core Predicates and Pseudo-Random Numbers

We have seen several functions $f$ with the property that $f(x)$was easy to compute but $f^{-1}$ was difficult. Such an $f$ is called a one-way function.¹⁶ A predicate is a property $B$ which is true or false for any $x$. Typical examples might be ``is an odd number'' or ``is $\le50$.'' A hard-core predicate for a function $f$ is a predicate such that

1.

there is an efficient algorithm for deciding whether $B(x)$ is true

2.

if we are given $f(x)$, there is no efficient algorithm for guessing whether $B(x)$ is true which has a probability much greater than $1/2$ of being right.

The example we used in the quadratic number generator was

$$f(x)\equiv x^2\hbox{ mod }n\qquad B(x)=\hbox{ \lq\lq $x$ is odd''}$$

where we are looking only at those $x$ which are squares.

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

$$B(x)\quad B(f^{-1}(x))\quad B(f^{-1}(f^{-1}(x))) \dots$$

satisfies the Next Bit Condition.

As a corollary, the sequence $B(x)$, $B(f(x))$,...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 $B(x)$ with $f(x)$ known by asking the next-bit predictor what would occur next in the sequence

$$B(f^{(k)}(x))\quad B(f^{(k-1)}(x)\dots B(f(f(x)))\quad B(f(x))$$

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

Footnotes

... function.¹⁶

In later work, we will be defining a one-way function to be such that there is no efficiently computable $g$ with $g(x)=f^{-1}(x)$ for most $x$.