Next: A recent pseudo-random number
Up: Further results on pseudo-random
Previous: Hard-Core Predicates and Pseudo-Random
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
Translated from LaTeX by Scott Sutherland
1998-03-15