Cryptography Reference
In-Depth Information
Exercise 12:
Prove that pseudorandom generators do not assign noticeable probabil-
ity mass to any string. That is, if Gis a pseudorandom generator, then for every positive
polynomial pand all sufficiently large nand
α
,Pr[G(U
n
)
=
α
]
<
1
/
p(n).
Exercise 13:
Do pseudorandom generators induce
1-1
mappings? That is, if G is
a pseudorandom generator, is it the case that the mapping G:
n
l(n)
{
0, 1
}
→{
0, 1
}
is 1-1?
1.
Show that if pseudorandom generators exist, then there exist pseudorandom generators
Gsuch that the mapping G:
{
0, 1
}
l(n)
is not 1-1.
2.
Show that if one-way permutations exist, then there exist pseudorandom generators G
such that the mapping G:
{
0, 1
}
n
→{
0, 1
}
n
→{
0, 1
}
l(n)
is 1-1.
Exercise 14:
Let G be a pseudorandom generator, and let h be a polynomial-time-
computable permutation (over strings of the same length). Prove that G
and G
defined
by G
(s)
def
h(G(s)) and G
(s)
def
G(h(s)) are both pseudorandom generators.
=
=
Exercise 15:
Suppose that Gis a pseudorandom generator, and consider the follow-
ing modifications to it:
1.
G
(s)
def
=
0
|
G(s)
|
if the number of 1's in sis exactly
|
s
|/
2, and G
(s)
def
=
G(s) otherwise.
2.
G
(s)
def
=
0
|
G(s)
|
if the number of 1's in sis exactly
|
s
|/
3, and G
(s)
def
=
G(s) otherwise.
Which of these is a pseudorandom generator?
Exercise 16:
Analogously to Exercise 9 in Chapter 2, refute the following conjecture:
For every pseudorandom generator G, the function G
(s)
def
=
G(s)
⊕
s0
|
G(s)
|−|
s
|
is
also a pseudorandom generator.
Guideline:
Let g be a pseudorandom generator, and consider G defined on pairs of
strings of the same length such that G(r, s)
=
(r, g(s)).
Exercise 17:
Amoregeneraldefinitionofapseudorandomgenerator: The following
definition deviates from the standard one by refraining from the length-regular require-
ment regarding the generator (i.e., it is not required that
|
G(x)
|
=
|
G(y)
|
for all
|
x
|
=
|
y
|
).
A
generalpseudorandomgenerator
is a deterministic polynomial-time algorithm Gsatis-
fying the following two conditions:
Expansion: For every s
∈{
0, 1
}
∗
, it holds that
|
G(s)
| > |
s
|
.
Pseudorandomness (as in Definition 3.3.1): The ensemble
{
G(U
n
)
}
n
∈
N
is pseudo-
random.
Prove the following statements:
1.
If there exists a general pseudorandom generator, then there exists a standard one.
2.
Let Gbe a general pseudorandom generator, and let l : N
→
N be such that
{
G(U
n
)
}
n
∈
N
is polynomial-time-indistinguishable from
{
U
l(n)
}
n
∈
N
.
(a)
Prove that l(n)
>
nholds for all but finitely many n's.
(b)
Prove that the probability that G(U
n
) has length not equal to l(n) is negligible (in n).
Guideline (Part 2b):
The difficult case is when l(n) is not computable in poly(n) time
from n(otherwise, one can simply compare the length of the tested string to l(n)). In the
