Next: A recent pseudo-random number Up: Further results on pseudo-random Previous: Hard-Core Predicates and Pseudo-Random   Contents

Construction of hard-core predicates

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 result17 interesting.

Theorem 33   Let be a one-way function which maps sequences of bits of length to sequences of length . For each and -bit define to be true if the number of 1's in positions in specified by is even. There is no efficient algorithm which can guess given and with probability much greater than .

This result does not rule out the possibility that, for some specific , it may be possible to guess in an efficient way. However, it would not be possible to do something like guess with probability for of all possible , and probability for all other . [this would imply we would be correct about overall with probability ]

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 .

Theorem 34   Suppose that for at least of all . We can enumerate in time polynomial in such that with probability close to 1.

To deduce Theorem 33 from Theorem 34, suppose we had an efficient algorithm for guessing . We obtain , which cannot be too large given the time bound. If we are given the value of , we can evaluate for all to identify the correct with high probability, which would mean is not a one-way function.

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
 (5)

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 .

Lemma 35   For any , , where the sum is over all .

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

Footnotes

... result17
O. Goldreich and L. Levin, A Hard-Core Predicate for Every One-Way Function,'' Symposium on Theory of Computation (1989)

Next: A recent pseudo-random number Up: Further results on pseudo-random Previous: Hard-Core Predicates and Pseudo-Random   Contents
Translated from LaTeX by Scott Sutherland
2002-12-14