Cryptography Reference
In-Depth Information
Multiplying the above conditional probability with P(S
r−1
[r] = r), we get the
result.
N−2
N(N−1)
z
r
= 0 & S
r−1
[r] = r
Lemma 6.2.8. For 3 ≤ r ≤ 255, P
=
(1 −
p
r−1,r
).
Proof: Here, instead of splitting the joint probability into the product
of one marginal probability and one conditional probability, we proceed to
calculate directly as follows.
z
r
= 0 & S
r−1
[r] = r
P
S
r
[S
r
[r] + S
r−1
[r]] = 0 & S
r−1
[r] = r
= P
P(S
r
[S
r
[r] + y] = 0 & S
r−1
[r] = y)
=
y=r
N−1
S
r
[x + y] = 0 & S
r
[r] = x & S
r−1
[r] = y
=
P
y=r
x=0
Consider a special case, namely, x = r−y. In this case, S
r
[x+y] = S
r
[r] = 0
for the first event and S
r
[r] = x = r−y = 0 for the second event (note that
y = r). This poses a contradiction (an event with probability of occurrence
0), and hence one can write
z
r
= 0 & S
r−1
[r] = r
P
S
r
[x + y] = 0 & S
r
[r] = x & S
r−1
[r] = y
=
P
y=r
x=r−y
S
r−1
[r] = y
S
r
[x + y] = 0 & S
r
[r] = x
=
P
P
, (6.3)
y=r
x=r−y
where the last expression results from the fact that the events (S
r
[x+y] = 0)
and (S
r
[r] = x) are both independent of (S
r−1
[r] = y), since a state update
has occurred in the process, with a swap involving the index r.
Similar to the derivation of Equation (6.2), we obtain
S
r
[x + y] = 0 & S
r
[r] = x
0
if x = 0,
P
=
(6.4)
1
N(N−1)
if x = 0.
Note that in the case x = 0, simultaneous occurrence of the events (S
r
[x+y] =
S
r
[y] = 0) and (S
r
[r] = x = 0) pose a contradiction, as the two locations y
and r of S
r
are distinct (since y = r), and they can not have the same value
0.
