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