Cryptography Reference
In-Depth Information
gives a detailed description of the interleaving of the two random processes (
and can be
skipped
). We consider a randomized process
mapping sequences of
n
-bit strings (repre-
senting the history) to single
m
-bit strings. We stress that
ρ
is
not
necessarily memoryless
(and hence may “remember” its previous random choices). Namely, for every fixed se-
quence
v
1
,...,v
i
∈{
0
,
1
}
ρ
n
, the random variable
ρ
(
v
1
,...,v
i
) is (arbitrarily) distributed
m
over
{
0
,
1
}
∪{⊥}
, where
⊥
is a special symbol denoting termination. A “random” func-
m
n
tion
g
:
{
0
,
1
}
→{
0
,
1
}
is defined by iterating the process
ρ
with the random process
ψ
starts with
g
that is undefined on every point in its domain.
At the
i
th iteration,
ψ
lets
p
i
defined next. Process
ψ
def
=
ρ
(
v
1
,...,v
i
−
1
) and, assuming
p
i
= ⊥
, sets
v
i
def
=
v
j
if
n
otherwise. In the
latter case (i.e.,
p
i
is new, and hence
g
is not yet defined on
p
i
),
ψ
sets
g
(
p
i
)
def
p
i
=
p
j
for some
j
<
i
, and lets
v
i
be uniformly distributed in
{
0
,
1
}
=
v
i
(in
fact,
g
(
p
i
)
terminates (i.e.,
ρ
(
v
1
,...,v
T
)
=⊥
for some
T
), process
ψ
completes the function
g
(if necessary) by
choosing independently and uniformly in
=
g
(
p
j
)
=
v
j
=
v
i
also in case
p
i
=
p
j
for some
j
<
i
). When
ρ
n
values for the points at which
g
is still
undefined. (Alternatively, we can augment the process
ρ
so that it terminates only after
specifying all possible
m
-bit strings.)
Once a function
g
:
{
0
,
1
}
m
n
f
g
:
{
,
}
→{
,
}
0
1
0
1
is totally defined, we define a function
n
n
{
0
,
1
}
→{
0
,
1
}
by
σ
m
···
σ
1
))
···
The reader can easily verify that
f
g
equals
f
g
(0
m
)
,...,
g
(1
m
)
(as defined in the hybrid con-
struction earlier). Also, one can easily verify that the preceding random process (i.e.,
the interleaving of
G
σ
n
···
G
σ
m
+
2
G
σ
m
+
1
(
g
(
σ
1
σ
2
···
σ
n
)
def
f
g
(
=
) yields a function
g
that is uniformly distributed over
the set of all possible functions mapping
m
-bit strings to
n
-bit strings. It follows that
the previously described random process yields a result (i.e., a function) that is distributed
identically to the random variable
H
n
.
Suppose now that the checkpoint chosen by
D
equals
k
and that
D
's inputs are inde-
pendently and uniformly selected in
ψ
with any
ρ
2
n
. In this case the way in which
D
answers
M
's queries can be viewed as placing independently and uniformly selected
n
-bit strings
as the labels of the (
k
{
0
,
1
}
1)-level vertices. It follows that the way in which
D
answers
M
's
queries corresponds to the previously described process with
m
=
k
+
1 (with
M
playing
the role of
+
ρ
and
A
playing the role of
ψ
). Hence, in this case,
M
is invoked with access
to the
k
+
1 hybrid random variable.
Suppose, on the other hand, that (again the checkpoint chosen by
D
equals
k
and that)
D
's inputs are independently selected so that each is distributed identically to
G
(
U
n
). In
this case the way in which
D
answers
M
's queries can be viewed as placing independently
and uniformly selected
n
-bit strings as the labels of the
k
-level vertices. It follows that
the way in which
D
answers
M
's queries corresponds to the previously described process
with
m
k
. Hence, in this case
M
is invoked with access to the
k
th hybrid random
variable.
=
[
M
H
n
(1
n
)
=
1]
−
Pr
[
M
H
n
(1
n
)
=
1], it
Combining Claim 3.6.6.1 and
(
n
)
=
Pr
follows that
D
G
U
(1
n
G
U
(
t
n
1
D
U
(1)
2
n
2
n
1
U
(
t
)
Pr
−
Pr
,...,
=
,...,
=
1
n
M
H
n
(1
n
)
=
1
1
n
(1
n
)
=
1
n
−
1
n
−
1
k
=
0
Pr
k
=
0
Pr
M
H
k
+
1
=
−
n
=
(
n
)
n
