Cryptography Reference
In-Depth Information
general case, first prove that there exists a function l : N N such that the probability
that | G(U n ) | = l (n) is negligible (in n). (Hint: Otherwise, one could distinguish polynomial
products of G(U n ) from polynomial products of U l(n) .) Next prove that l (n) = l(n) by con-
sidering a distinguisher that on input 1 n and a string to be tested, α , first samples G(U n )
and compares its length to |α| .
Exercise 18: Consider a modification of Construction 3.3.2, where s i σ i = G 1 (s i 1 )is
used instead of
σ i s i =
G 1 (s i 1 ). Provide a simple proof that the resulting algorithm is
also pseudorandom.
Guideline: Do not modify the proof of Theorem 3.3.3, but rather modify G 1 itself.
Exercise 19: Alternative construction of pseudorandom generator with large expan-
sion factor: Let G 1 be a pseudorandom generator with expansion factor l(n)
n
1,
=
+
and let p(
·
) be a polynomial. Define G(s) to be the result of applying G 1 iteratively p(
|
s
|
)
times on s(i.e., G(s) def
(s), where G 1 (s) def
def
=
G p( | s | )
1
sand G i + 1
1
G 1 (G 1 (s))).
=
=
Prove that Gis a pseudorandom generator.
What are the advantages of using Construction 3.3.2?
Exercise 20: Analternativedefinitionofunpredictableensembles: Consider a modifi-
cation to Definition 3.3.6 in which the quantification is over only (probabilistic polynomial-
time) algorithms that never read the entire input. That is, in every execution of such an
algorithm A, on input (1 | x | , x), algorithm A reads at most
|
x
|−
1 bits of x. Prove that
the modified definition is equivalent to the original one.
Guideline: Since the scope of the modified definition is smaller that the scope of the
original one, we need only show how to convert an arbitrary probabilistic polynomial-time
algorithm A into one that never reads the entire input and still has at least the same
success probability in predicting the next bit. This can be done by emulating A without
ever reading the last input bit, so that whenever Atries to read the last input bit, we halt
with a uniformly selected output bit. (Otherwise, we faithfully emulate A.) Note that in
case Areads its last input bit, its output-prediction bit is correct with probability 1 2 (by the
fictitious definition of next A in this case; see Definition 3.3.6). This success probability is
met by our modified algorithm that outputs a uniformly selected bit as a guess of the last
input bit.
Exercise 21: On-line pseudorandom generator: Recall that variable-output pseu-
dorandom generators (see Section 3.3.3) are deterministic polynomial-time programs
that when given a random seed will produce an infinite sequence of bits such that every
polynomially long prefix of it will be pseudorandom. On-line pseudorandom genera-
tors are a special case of variable-output pseudorandom generators in which a hidden
state is maintained and updated so as to allow generation of the next output bit in time
polynomial in the length of the seed, regardless of the number of bits generated thus
far. On-line pseudorandom generators are defined through their next-stepfunctionthat
maps the current state of the generator to a pair consisting of an output bit and a next
state. That is, a polynomial-time algorithm g mapping n-bit-long strings to (n
1)-bit-
long strings is called a next-step function of an on-line pseudorandom generator if for
every polynomial pthe ensemble { G n } n N is pseudorandom, where G n is defined by
the following random process:
+
Search WWH ::




Custom Search