Cryptography Reference
In-Depth Information
Proof: The event (j
r+2
= i
r+2
+ j
r+1
−j
r
) can occur in two ways.
Case I: j
r+1
= i
r
+ 2. By Lemma 5.4.4,
j
r+2
−j
r
= j
r+1
+ (i
r
2j
r+1
=
+ 2)−j
r
.
Thus, the contribution of this part is
1
N
.
P(j
r+1
= i
r
+ 2) =
Case II: j
r+1
= i
r
+ 2 and still j
r+2
= i
r+2
+ j
r+1
− j
r
due to random
association. The probability contribution of this part is
1−
1
N
1
1
N
.
N −1
=
Adding the above two contributions, we get the result.
Since S
r+2
[j
r+2
] = S
r+1
[i
r+2
] = j
r+2
−j
r+1
, we immediately arrive at the
following corollary.
2
Corollary 5.4.7. P(j
r
N
, r ≥ 0.
Now we show further leakage (different than Corollary 5.4.2) of information
about the pseudo-random index j from z.
= i
r+2
−S
r+2
[j
r+2
]) =
1
2
Theorem 5.4.8. P(z
r+2
= j
r
) =
N
), r ≥ 0.
Proof: The event (z
r+2
= j
r
) can occur in two possible ways.
Case I: Consider the events
N
(1 +
z
r+2
= i
r+2
−S
r+2
[j
r+2
]
and
−S
r+2
[j
r+2
].
By Theorem 5.2.1 and Corollary 5.4.7, the probability contribution of
this part is
j
r
= i
r+2
2
N
2
4
N
2
.
N
=
Case II: Consider that
−S
r+2
[j
r+2
]
and still z
r+2
= j
r
due to random association. The probability contri-
bution of this part is
= i
r+2
z
r+2
1−
2
N
1
N
.
