It seems much harder to find examples of hard-core predicates
than of one-way functions. The latter can be obtained from
discrete logarithms, subset-sum problems, and elsewhere.
It is difficult to prove that a property cannot be guessed
with probability much larger than . This makes the
following result^{17} interesting.

To prove this, we shall consider the following scenario: We are trying to determine an unknown . We have an oracle which is supposed to tell us . The oracle may lie, but must tell the truth more than half the time. Theorem 34 says we can efficiently enumerate a not-too-large set which probably includes .

The construction of proceeds in stages. At stage (), we enumerate which includes (with probability close to 1) the first digits of .

We will consider fixed for the rest of this section.
Define
and
.
If and are true or false,
is defined to be 1 if and are both
true or both false, 0 otherwise. If is defined for all ,
we will use
to represent the average value of ,
in other words,
, with similar definitions for
other collections of . The
hypothesis of Theorem 34 can be written as

Let . If there is a with [i.e., is the first bits of ], then

Recall that is true if and only if the sum of the bits of corresponding to is even. This implies

Thus, if , then

To test whether a given satisfies (5) requires looking at all possible and , which would take too much time. However, as in section 7.3, we can take not-too-large random samples from all possible and , with a high probability of correctly deciding whether satisfies (5). Let be the number of different used in the sampling.

At stage , we have obtained which includes the first bits of with high probability. To create , we take each member of , add 0 and 1 to it, and identify using sampling which of the resulting -bit strings satisfy (5).

This process would take too much time if the number of strings doubled at each step. To complete the proof, we use Lemma 35 to show that, for every , the number of with is not too large, specifically there are at most such . In order to to be included in , must satisfy for at least one of the sets used in the sample, which gives a bound of on .

**Proof:** is a constant and may be ignored. We will argue by
induction on . Define
.
The function may be represented by
with

We divide according to whether or 1 to obtain

- ... result
^{17} - O. Goldreich and L. Levin, ``A Hard-Core
Predicate for Every One-Way Function,''
*Symposium on Theory of Computation*(1989)

2002-12-14