Cryptography Reference
In-Depth Information
n
.
For i
=
1to p(n), do
σ
i
·
s
i
←
g(s
i
−
1
), where
σ
i
∈{
0, 1
}
(and s
i
∈{
0, 1
}
Uniformly select s
0
∈{
0, 1
}
n
).
Output
σ
1
σ
2
···σ
p(n)
.
That is, s
0
is the initial (random) state of the on-line pseudorandom generator, and s
i
is its state after outputting i bits. (Indeed, the definition of this ensemble is similar to
Construction 3.3.2.)
1.
Prove that if G is an ordinary pseudorandom generator with expansion function
(n)
=
n
+
1, then it also constitutes a next-step function of an on-line pseudorandom generator.
Guideline:
Use the similarity mentioned earlier.
2.
Show that the converse does not necessarily hold; that is, if gis the next-step function of
an on-line pseudorandom generator, then it is not necessarily a pseudorandom generator.
Guideline:
Given a next-step function g
, consider the next-step function g(s
·
r)
=
g
(s)
0
|
r
|
for (say)
.
3.
Still, show that given any (next-step function g of an) on-line pseudorandom generator,
one can easily construct a pseudorandom generator.
Guideline:
Just activate the on-line generator enough times.
This definition of (a next-step function of) an on-line pseudorandom generator guar-
antees that the current state of the generator does not grow in size/length with the
number of bits generated. We next consider a somewhat relaxed definition that al-
lows moderate growth in the size/length of the current state. For example, consider a
relaxed definition of an on-line pseudorandom generator that allows (polynomial-time-
computable) next-step functions g that map m-bit-long strings to (m
+
O(1))-bit-long
strings. (The distribution considered is again defined by selecting s
0
uniformly in
·
|
r
|
=
|
s
|
n
,
{
0, 1
}
letting
σ
i
·
s
i
=
g(s
i
−
1
), where
σ
i
∈{
0, 1
}
, and outputting
σ
1
σ
2
···σ
p(n)
; however, here
|
s
p(n)
|
=
|
s
0
|
, unless
|
g(s)
|
=
|
s
|
+
1 as before.)
Show that using the relaxed definition of an on-line pseudorandom generator does
not guarantee that each next output bit will be generated in time polynomial in the
length of the seed (i.e., regardless of the number of bits generated thus far).
Show that the foregoing Item 3 still holds.
Let gbe the next-step function of a relaxed on-line pseudorandom generator, and let
T
g
(m) denote the complexity of computing gon inputs of length m. Provide an upper
bound on the complexity of producing t(n) bits out of an n-bit seed in the relaxed on-
line pseudorandom generator based on g. Compare this bound to the one obtained
for a non-relaxed on-line pseudorandom generator.
How much can we allow the current state to grow at each step so as to maintain
polynomial-time operation when outputting polynomially many bits?
Exercise 22:
Constructions of hashing families: We associate
-dimensional binary
vectors with
-bit-long strings.
1.
Consider the set S
n
of functions mapping n-bit-long strings into m-bit strings. A function
h
A,b
in S
n
is represented by a pair ( A, b), where A is an n-by-m binary matrix and b is
an m-dimensional binary vector. The n-dimensional binary vector x is mapped by the
function h
A,b
to the m-dimensional binary vector resulting from multiplying x by A and
adding the vector b to the resulting vector (i.e., h
A,b
(x)
=
xA
+
b). Prove that S
n
so
defined constitutes a hashing family (as defined in Section 3.5.1.1).
