Cryptography Reference
In-Depth Information
w
x
X
·E[p
x
(1−p)
w−x
· (C
p
(w,x))
2
] = w
(1.17)
x=0
This completes the proof of the lemma.
The following lemma is quite critical and its proof is the one that primarily
accounts for the particular choice of the p distribution.
Lemma 1.25. For any w ∈ N and x ∈{0,1,..
.
,w}, and p = sin
2
(r) where r
is uniform over [t
0
,π/2−t
0
] with t
0
= arcsin(
√
t) and t ∈ (0,
2
), it holds that
H
x
= E[p
x
(1−p)
w−x
·C
p
(w,x)]
=
π−4t
0
· ((1−t)
x
t
w−x
−t
x
(1−t)
w−x
)
1
Proof. By definition we have
E[p
x
(1−p)
w−x
· (xq− (w−x)/q))]
=
π/2−2t
0
·
R
π/2−t
0
1
sin
2x
r cos
2(w−x)
r(xcot r− (w−x) tanr)dr
t
0
π/2−2t
0
· [
2
sin
2x
r cos
2(w−x)
r]
π/2−t
0
1
=
t
0
from which the statement of the lemma follows easily.
M
x
. Given that e
u
≤
1+u+u
2
for any u < 1.7, assume that α is selected so that −αC
p
(w,x) < 1.7
for all feasible choices of p,x. It follows that:
We next proceed to provide a bound for
P
x=0
x
e
−α·C
p
(w,x)
≤ 1−α·C
p
(w,x) + α
2
· (C
p
(w,x))
2
under the condition that
√
p,w
C
p
(w,x) < 1.7 ⇐= α <
1.7
t
α·max
(1.18)
w
Based on this we obtain that for x ∈{1,...,w−1},
M
x
≤ max{Z
x
±α·H
x
+ α
2
Q
x
}≤ Z
x
+ α·|H
x
|+ α
2
Q
x
while,
M
0
≤ Z
0
+ α·H
0
+ α
2
·Q
0
and M
w
≤ Z
w
−α·H
w
+ α
2
·Q
w
It follows that
w
x
X
X
w−
X
X
M
x
≤
|H
x
|) + α
2
·
Z
x
−α· (H
w
−H
0
−
Q
x
x=0
x=0
x=1
x=0
