Cryptography Reference
In-Depth Information
t
−
j
.
3.
Uniformly select
β
∈{
0
,
1
}
4.
Invoke
A
on input (1
t
,αβ
) and record the following values:
read by
A
,
(a)
in variable
, the length of the prefix of
αβ
, the output of
A
.
(b)
in variable
τ
5.
If
=
j
, then halt with output
τ
.
6.
Otherwise (i.e.,
=
j
), output a uniformly selected bit.
Clearly,
A
is implementable in probabilistic polynomial time. We now ana-
lyze the success probability of
A
in predicting
b
(
U
n
) when given
f
(
U
n
). A
key observation is that on input
f
(
U
n
), for each possible value assigned to
j
in
Step 1 the value of
α
(as determined in Step 2 of
A
) is distributed identically
to the
j
-bit-long prefix of the distribution
G
(
U
n
). This is due to the fact that
f
induces a permutation over
{
0
,
1
}
n
, and so
b
(
f
j
−
1
(
U
n
))
···
b
(
U
n
) is distributed
identically to
b
(
f
t
−
1
(
U
n
))
b
(
f
t
−
j
(
U
n
)). We use the following notations and
···
observations:
j
−
1
(
y
))
Let
R
j
be a randomized process that, given
y
, outputs
b
(
f
···
b
(
y
)
·
r
,
t
−
j
.
Note that on input
y
, after selecting
j
in Step 1, algorithm
A
invokes
A
on
input (1
t
where
r
is uniformly distributed in
{
0
,
1
}
R
j
(
y
)). By the foregoing (“key”) observation, the
j
-bit-long prefix of
R
j
(
f
(
U
n
)) is distributed identically to the
j
-bit-long prefix of
G
(
U
n
). Also note
that
b
(
f
,
j
−
1
(
f
(
U
n
)))
1)-
bit-long prefix of
G
(
U
n
) and that the former is obtained by concatenating the
j
-bit-long prefix of
R
j
(
f
(
U
n
)) with
b
(
U
n
).
···
b
(
f
(
U
n
))
·
b
(
U
n
) is distributed identically to the (
j
+
γ
γ
∈{
,
}
t
Let
L
A
(
) be a random variable representing the length of the prefix of
0
1
read by
A
on input (1
t
).
Note that the behavior of
A
on input (1
t
,γ
,γ
) depends only on the
L
A
(
γ
) first
bits of
γ
(and is independent of the
t
−
L
A
(
γ
) last bits of
γ
). On the other hand,
next
A
(
γ
) equals the
L
A
(
γ
)
+
1 bit of
γ
.
Let
J
be a random variable representing the random choice made in Step 1, and
let
U
1
represent the random choice made in Step 6. Recall that
U
1
is uniformly
distributed in
{
0
,
1
}
, independently of anything else.
J
, then
A
outputs the value
A
(1
t
), and otherwise
A
Note that if
L
A
(
γ
)
=
,γ
outputs
U
1
.
Using all the foregoing, we get
[
A
(
f
(
U
n
))
=
b
(
U
n
)]
=
Pr
Pr
[
A
(1
t
,
R
J
(
f
(
U
n
)))
=
b
(
U
n
)&
L
A
(
R
J
(
f
(
U
n
)))
=
J
]
+
Pr
[
U
1
=
b
(
U
n
)&
L
A
(
R
J
(
f
(
U
n
)))
=
J
]
[
A
(1
t
G
(
U
n
))
next
A
(
G
(
U
n
)) &
J
L
A
(
G
(
U
n
))]
=
Pr
,
=
=
1
2
where we use the fact that when
L
A
(
R
J
(
f
(
U
n
)))
=
J
, the behavior of
A
depends only on the
J
-bit-long prefix of
R
J
(
f
(
U
n
)), which in turn is distributed
130
+
Pr
[
J
=
L
A
(
G
(
U
n
))]
·
