Cryptography Reference
In-Depth Information
Second Proof of Theorem 3.4.1:
Recall that
G
(
U
n
)
=
f
(
U
n
)
·
b
(
U
n
) and that our
goal is to prove that the ensembles
{
U
n
+
1
}
n
∈N
are polynomial-
time-indistinguishable. We first note that the
n
-b
it-long prefix of
f
(
U
n
)
{
G
(
U
n
)
}
n
∈N
and
·
b
(
U
n
)is
n
. Thus, letting
b
(
x
)
def
uniformly distributed in
{
0
,
1
}
=
1
−
b
(
x
), all that we need
to
prove is that the ensembles
E
(1)
def
={
f
(
U
n
)
·
b
(
U
n
)
}
n
∈N
and
E
(2)
def
={
f
(
U
n
)
·
b
(
U
n
)
}
n
∈N
are polynomial-time-indistinguishable (since
{
U
n
+
1
}
n
∈N
is distributed
identically to the ensemble obtained by taking
E
(1)
1
2
, and
E
(2)
with probability
otherwise).
Further justification of the foregoing claim:
First, note that
E
(1)
is identical
to
{
G
(
U
n
)
}
n
∈N
. Next note that
{
U
n
+
1
}
n
∈N
is distributed identically to the ensemble
{
U
1
}
n
∈N
, where
U
n
and
U
1
are indepe
nd
ently random variables. Thinking
of
U
1
as being uniformly distributed in
{
b
(
U
n
)
,
b
(
U
n
)
}
, we observe that
f
(
U
n
)
·
U
1
is distributed identically to the distribu
ti
on obtained by taking
E
(1)
f
(
U
n
)
·
def
=
f
(
U
n
)
·
b
(
U
n
)
n
def
=
f
(
U
n
)
2
, and
E
(2)
1
·
b
(
U
n
) otherwise. Thus, for every algorithm
D
,
with probability
n
Pr
[
D
(
U
n
+
1
)
=
1]
=
Pr
[
D
(
f
(
U
n
)
·
U
1
)
=
1]
2
·
Pr
D
E
(1
n
=
1
+
2
·
Pr
D
E
(2
n
=
1
1
1
=
It follows that
Pr
−
Pr
[
D
(
G
(
U
n
))
=
1]
[
D
(
U
n
+
1
)
=
1]
1
2
·
Pr
D
E
(2
n
=
1
=
Pr
D
E
(1
n
=
1
−
2
·
Pr
D
E
(1
n
=
1
+
1
2
·
Pr
D
E
(1
n
=
1
−
Pr
D
E
(2
n
=
1
1
=
Thus, in order to show that an algorithm
D
does not distinguish the ensembles
{
G
(
U
n
)
}
n
∈N
and
{
U
n
+
1
}
n
∈N
, it suffices to show that
D
does not distinguish the en-
sembles
E
(1)
and
E
(2)
.
We n
ow
prove that the ensembles
E
(1)
={
f
(
U
n
)
·
b
(
U
n
)
}
n
∈N
and
E
(2)
=
{
}
n
∈N
are polynomial-time-indistinguishable. We do so by sim-
plifying the argument presented in the proof of Theorem 3.3.7. That is, us-
ing any algorithm (denoted
D
) that distinguishes
E
(1)
and
E
(2)
, we construct
a predictor (denoted
A
)of
b
(
U
n
) based on
f
(
U
n
). We assume, to the contradic-
tion and without loss of generality, that for some polynomial
p
and infinitely
many
n
's,
f
(
U
n
)
·
b
(
U
n
)
1
p
(
n
)
Pr
[
D
(
f
(
U
n
)
·
b
(
U
n
))
=
1]
−
Pr
[
D
(
f
(
U
n
)
·
b
(
U
n
))
=
1]
>
(3.12)
Using
D
as a subroutine, we construct an algorithm
A
as follows. On input of
y
=
f
(
x
), algorithm
A
proceeds as follows:
1.
Select
σ
uniformly in
{
0
,
1
}
.
2.
If
D
(
y
·
σ
)
=
1, then output
σ
, and otherwise output 1
−
σ
.
