Cryptography Reference
In-Depth Information
's and
U
(
j
)
where the
U
(
i
)
n
2
n
's are independent random variables uniformly dis-
tributed over
2
n
, respectively.
Claim 3.6.6.1 is quite obvious; yet a rigorous proof is more complex than
one might realize at first glance, the reason being that
M
's queries may depend
on previous answers it has received, and hence the correspondence between the
inputs of
D
and possible values assigned to the hybrids is less obvious than it
seems. To illustrate the difficulty, consider an
N
-bit string that is selected by a pair
of interactive processes that proceed in
N
iterations. At each iteration, the first
process chooses a new location (i.e., an unused
i
{
0
,
1
}
n
and
{
0
,
1
}
) based on the entire
history of the interaction, and the second process sets the value of this bit (i.e., the
i
th bit) by flipping an unbiased coin. It is intuitively clear that the resulting string
is uniformly distributed; still, a proof is required (since randomized processes
are subtle entities that often lead to mistakes). In our setting, the situation is
slightly more involved. The process of determining the string is terminated after
T
<
N
iterations, and statements are made regarding the resulting string that is
only partially determined. Consequently, the situation is slightly confusing, and
we feel that a detailed argument is required. However, the argument provides no
additional insights and can be skipped without significant damage (especially by
readers who are more interested in cryptography than in “probabilistic analysis”).
∈{
1
,...,
N
}
Proof of Claim 3.6.6.1:
We start by sketching a proof of the claim for the extremely
simple case in which
M
's queries are the first
t
strings (of length
n
) in lexicographic order.
Let us further assume, for simplicity, that on input
α
1
,...,α
t
, algorithm
D
happens to
choose checkpoint
k
such that
t
=
2
k
+
1
. In this case the oracle machine
M
is invoked on
input 1
n
2
k
and access to the function
f
s
1
,...,
s
2
k
+
1
, where
s
2
j
−
1
+
σ
=
P
σ
(
α
j
) for every
j
≤
2
n
, then
M
is
and
σ
∈{
0
,
1
}
. Thus, if the inputs to
D
are uniformly selected in
{
0
,
1
}
invoked with access to the
k
1 hybrid random variable (since in this case the
s
j
's are
independent and uniformly distributed in
{
0
,
1
}
+
n
). On the other hand, if the inputs to
D
are distributed as
G
(
U
n
), then
M
is invoked with access to the
k
th hybrid random variable
(since in this case
f
s
1
,...,
s
2
k
+
1
=
f
r
1
,...,
r
2
k
, where the
r
j
's are seeds corresponding to the
α
j
's).
For the general case, we consider an alternative way of defining the random variable
H
n
for every 0
n
. This alternative way is somewhat similar to the way in which
D
answers the queries of the oracle machine
M
. (We use the symbol
m
instead of
k
, since
m
does not
necessarily equal the checkpoint (denoted
k
) chosen by algorithm
D
.) This way
of defining
H
n
consists of the interleaving of two random processes, which together first
select at random a function
g
:
{
0
,
1
}
≤
m
≤
m
n
→{
0
,
1
}
that is later used to determine a function
n
n
. The first random process, denoted
, is an arbitrary process (“given to
us from the outside”) that specifies points in the domain of
g
. (The process
ρ
corresponds
to the queries of
M
, whereas the second process corresponds to the way
A
answers these
queries.) The second process, denoted
ψ
, assigns uniformly selected
n
-bit-long strings to
every new point specified by
f
:
{
0
,
1
}
→{
0
,
1
}
ρ
, thus defining the value of
g
at this point. We stress that in
case
ρ
specifies an old point (i.e., a point for which
g
is already defined), then the second
process does nothing (i.e., the value of
g
at this point is left unchanged). The process
ρ
ρ
may depend on the history of the two processes and in particular on the values chosen for
the previous points. When
) selects random values
for the remaining undefined points (in case such exist). We stress that the second process
(i.e.,
ψ
) is fixed for all possible choices of a (“first”) process
ρ
. The rest of this paragraph
155
ρ
terminates, the second process (i.e.,
ψ
