Cryptography Reference
In-Depth Information
2.
Show that one direction in Part 1 does not hold in general (i.e., for super-logarithmically
growing l).
Comment: This exercise is related to Section 3.3.5.
Guideline (mainly for Part 1):
Assuming that there exists an algorithm A that violates
Eq. (2.16), construct an algorithm D
as in Definition 2.5.5 such that D
(y,
α
)
=
1if
and only if A(y)
=
α
. Show that the distinguishing gap of D
is at least s(n)
−
2
−
l(n)
,
where s(
) represents the success probability of A. On the other hand, assuming that
there exists an algorithm D
violating the condition in Definition 2.5.5, construct an al-
gorithm A that violates Eq. (2.16). Specifically, suppose, without loss of generality, that
Pr[D
( f(X
n
), h(X
n
))
·
1
p(n)
. Then, on
1]
Pr[D
( f(X
n
), R
l(n)
)
1]
+
ε
(n), where
ε
(n)
>
=
=
=
input y, algorithm A uniformly selects r
∈{
0, 1
}
l(n)
and r
∈
(
{
0, 1
}
l(n)
\{
r
}
), invokes
D
, and outputs r if D
(y, r)
1, and r
otherwise. Show that the success probability of
=
D
is at least
ε
(n)
2
l(n)
−
1
.
