Cryptography Reference
In-Depth Information
As in Section 10.2, the primed array name denotes the updated array,
when the two “+” operators are replaced by “⊕” in the update rule (Equa-
tion (10.1)). Hence,
10
=
10
⊕
20
⊕
33
⊕
18
,
(10.7)
P
′
[i⊟ 3]
P
−1
[i⊟ 3]
P[i⊟ 6]
P
−1
[i⊟ 514]
P[i⊟ 13]
8
=
8
⊕
18
⊕
31
⊕
16
,
(10.8)
P
′
[i⊟ 10]
P
−1
[i⊟ 10]
P[i⊟ 13]
P
−1
[i⊟ 521]
P[i⊟ 20]
23
and
P
′
−1
[i ⊟ 511]
31
.
(10.9)
Equations (10.7), (10.8) and (10.9) hold in ranges 13 ≤ i mod 512 < 514,
20 ≤ i mod 512 < 521 and 9 ≤ i mod 512 < 510 respectively.
XOR-ing both sides of Equations (10.6), (10.7), (10.8) and (10.9), and
rearranging terms, one gets, for 20 ≤ i mod 512 < 510,
23
⊕
33
⊕
46
⊕
=
P
−2
[i ⊟ 511]
P
−1
[i ⊟ 514]
P
−2
[i ⊟ 1022]
P
−1
[i ⊟ 521]
0
⊕
0
⊕
20
⊕
16
⊕
14
P[i]
P
−2
[i]
P[i ⊟ 6]
P[i ⊟ 20]
P
−2
[i ⊟ 510]
10
⊕
10
P
′
[i ⊟ 3]
=
P[i ⊟ 3]
8
⊕
8
P
′
[i ⊟ 10]
⊕
P[i ⊟ 10]
23
⊕
23
⊕
P
−1
[i ⊟ 511]
P
′
−1
[i ⊟ 511]
.
(10.10)
Lemma 10.3.6. For 1024τ + 20 ≤i < 1024τ + 510,
Prob
0
⊕
0
⊕
20
⊕
16
⊕
14
= 0
P[i]
P
−2
[i]
P[i ⊟ 6]
P[i ⊟ 20]
P
−2
[i ⊟ 510]
≈
1
27
.
Proof: From Equation (10.10), we can write the above probability as
Prob(λ
1
⊕λ
2
⊕λ
3
= 0)
where
10
⊕
10
,
P
′
[i ⊟ 3]
λ
1
=
P[i ⊟ 3]
8
⊕
8
,
P
′
[i ⊟ 10]
λ
2
=
P[i ⊟ 10]
23
⊕
23
.
P
′
−1
[i ⊟ 511]
λ
3
=
P
−1
[i ⊟ 511]
Now, from Lemma 10.2.3 (see Section 10.2), we get
Prob(λ
1
= 0) = Prob(λ
2
= 0) = Prob(λ
3
= 0) ≈
1
3
.
Now, XOR of three terms yield 0, if either all three terms are 0 or exactly
