Cryptography Reference
In-Depth Information
(by hypothesis,
j
i
). Then we record the current query (i.e.,
q
i
), but answer it
using the string associated with query
q
j
(i.e., the input string
<
α
j
). Namely, we
answer query
q
i
by
G
σ
n
···
G
σ
k
+
2
P
σ
k
+
1
(
α
j
)
···
where
q
i
=
σ
1
···
σ
n
. Finally, when machine
M
halts, algorithm
D
halts as well
and outputs the same output as
M
.
Pictorially, algorithm
D
answers the first query by first placing the two halves of
α
1
in the corresponding children of the tree's vertex reached by following the path
from the root corresponding to
σ
1
···
σ
k
. The labels of all vertices in the subtree
corresponding to
σ
1
···
σ
k
are determined by the labels of these two children
(as in the construction of
F
). Subsequent queries are answered by following
the corresponding paths from the root. In case the path does not pass through a
(
k
1)-level vertex that already has a label, we assign this vertex and its sibling
a new string (taken from the input). For the sake of simplicity, in case the path
of the
i
th query requires a new string, we use the
i
th input string (rather than the
first input string not used thus far). In case the path of a new query passes through
a(
k
+
1)-level vertex that has already been labeled, we use this label to compute
the labels of subsequent vertices along this path (and in particular the label of
the leaf). We stress that the algorithm
does not
compute the labels of
all
vertices
in a subtree corresponding to
+
σ
1
···
σ
k
(although these labels are determined by
the label of the vertex corresponding to
σ
1
···
σ
k
), but rather computes only the
labels of vertices along the paths corresponding to the queries.
Clearly, algorithm
D
can be implemented in polynomial time. It is left to
evaluate its performance. The key observation is the correspondence between
D
's actions on checkpoint
k
and the hybrids
k
and
k
+
1:
When the inputs are taken from the
t
(
n
)-product of
U
2
n
(and algorithm
D
chooses
k
as the checkpoint), the invoked machine
M
behaves exactly as on the
k
1
hybrid. This is so because
D
places halves of truly random 2
n
-bit-long strings at
level
k
+
+
1 (which is the same as placing truly random
n
-bit-long strings at level
k
+
1).
On the other hand, when the inputs are taken from the
t
(
n
)-product of
G
(
U
n
)
(and algorithm
D
chooses
k
as the checkpoint), then
M
behaves exactly as on
the
k
th hybrid. Indeed,
D
does not place the (unknown to it) corresponding seeds
(generating these pseudorandom strings) at level
k
; but putting the two halves of
the pseudorandom strings at level
k
+
1 has exactly the same effect.
Thus:
def
=
Claim 3.6.6.1:
Let
n
be an integer, and
t
t
(
n
). Let
K
be a random variable
describing the random choice of checkpoint by algorithm
D
(on input a
t
-long
sequence of 2
n
-bit-long strings). Then for every
k
∈{
0
,
1
,...,
n
−
1
}
,
D
G
U
(1
n
,...,
G
U
(
t
n
=
1
K
k
=
Pr
M
H
n
(1
n
)
1
Pr
=
=
D
U
(1)
2
n
2
n
=
1
K
=
k
=
Pr
M
H
k
+
1
(1
n
)
=
1
,...,
U
(
t
)
Pr
n
