Next: Construction of hard-core predicates
Up: Further results on pseudo-random
Previous: Further results on pseudo-random
Contents
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
- there is an efficient algorithm for deciding whether
is
true
- 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 sequence 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
Contents
Translated from LaTeX by Scott Sutherland
2002-12-14