Cryptography Reference
In-Depth Information
Claim 3.7.8.1:
For every
m
≥
1, conditioned on
¬
ζ
m
, the
R
i
's are uniformly and
independently distributed over
n
, and the
L
i
's are uniformly distributed over
the
n
-bit strings not assigned to previous
L
j
's. Namely, for every
{
0
,
1
}
α
1
,...,α
m
∈
{
0
,
1
}
n
,
1
2
n
m
i
=
1
R
i
=
α
i
¬
ζ
m
=
m
Pr
∧
(3.18)
whereas for every
distinct
β
1
,...,β
m
∈{
0
,
1
}
n
,
m
i
=
1
L
i
=
β
i
¬
ζ
m
=
1
Pr
m
∧
(3.19)
2
n
−
i
+
1
i
=
1
Proof Idea:
Eq. (3.18) follows from the observation that the
R
i
's are determined
by applying the random function
H
(3
n
to different arguments (i.e., the
R
i
's),
where the distinctness of the
R
i
's is implied by
¬
ζ
m
. Similarly, the
L
i
=
R
i
's
are determined by applying the random function
H
(2)
n
to different arguments (i.e.,
the
R
i
's), and
¬
ζ
m
also conditions the results (i.e., the
R
i
's) to be different. Thus,
Eq. (3.19) also holds.
Claim 3.7.8.2:
For every
m
≥
1,
2
m
2
n
Proof Idea:
Fixing any
i
≤
m
, we consider the probability that
R
m
+
1
=
R
i
. There
are two cases:
Pr
[
ζ
m
+
1
|¬
ζ
m
]
≤
1.
If
R
i
=
R
m
+
1
, then certainly (since (
L
i
,
R
i
)
(
L
m
+
1
,
R
m
+
1
)) we have
=
H
(1
n
R
i
=
H
(1
n
R
m
+
1
=
H
(1
n
R
m
+
1
=
R
i
=
L
i
⊕
L
i
⊕
L
m
+
1
⊕
R
m
+
1
2.
On the other hand, if
R
i
=
R
m
+
1
, then
Pr
R
i
=
R
m
+
1
= Pr
H
(1
n
R
i
⊕
H
(1
n
R
m
+
1
=
L
m
+
1
=
L
i
⊕
2
−
n
where the last equality holds because the random function
H
(1)
n
is applied to
different arguments (i.e.,
R
i
and
R
m
+
1
).
[
R
i
=
R
m
+
1
]
≤
2
−
n
. In similarity to the foregoing Case 2,
conditioned on
R
i
=
R
m
+
1
,wehave
Pr
Pr
Thus, in both cases,
R
i
=
R
m
+
1
=
Pr
H
(2
n
R
i
⊕
H
(2
n
R
m
+
1
=
R
i
⊕
R
m
+
1
=
2
−
n
Thus, for every
i
≤
m
,
R
m
+
1
R
i
=
R
i
=
R
m
+
1
≤
Pr
R
i
=
R
m
+
1
+
Pr
R
i
=
R
m
+
1
R
m
+
1
∨
R
i
=
Pr
≤
2
·
2
−
n
and the claim follows.
Using
Pr
[
ζ
m
]
≤
Pr
[
ζ
m
−
1
]
+
Pr
[
ζ
m
|¬
ζ
m
−
1
] and Claim 3.7.8.2, it follows, by induc-
m
2
tion on
m
, that
Pr
[
ζ
m
]
<
2
n
. By Claim 3.7.8.1, conditioned on
¬
ζ
m
, the answers
