Cryptography Reference
In-Depth Information
Proof: In round v + 1, i = v and j
v+1
= j
v
+ S
v
[v] + K[v]. The event
(S
v+1
[u] = v) can occur in two ways.
1. S
v
[u] already had the value v and the index u is not involved in the
swap in round v + 1.
2. S
v
[u] = v and the value v comes into the index u from the index v (i.e.,
S
v
[v] = v) by the swap in round v + 1.
From Proposition 3.2.5, we have
v
N −1
N
P(S
v
[v] = v) =
and also from Proposition 3.2.6, we get
v−u−1
1
N
N −1
N
P(S
v
[u] = v) =
.
Hence, except for the case “u = 0 and v = 1” (see Remark 3.2.8),
P(S
v+1
[u] = v)
= P(S
v
[u] = v)P(j
v
+ S
v
[v] + K[v] = u)
+P(S
v
[u] = v)P(S
v
[v] = v)P(j
v
+ S
v
[v] + K[v] = u)
v−u−1
1
N
N −1
N
N −1
N
=
v−u−1
v
1
N
1−
1
N
N −1
N
N −1
N
+
v−u
v
1
N
N −1
N
1
N
N − 1
N
=
+
2v−u−1
−
1
N
2
N −1
N
.
Remark 3.2.8. Case 1 in the proof of Lemma 3.2.7 applies to Lemma 3.2.4
also. In case 2, i.e., when S
v
[u] = v, in general we may or may not have
S
v
[v] = v. However, for u = 0 and v = 1,
(S
1
[0] = 1) ⇐⇒ (S
1
[1] = 1),
the probability of each of which is
N−
N
(note that there has been only one swap
involving the indices 0 and K[0] in round 1). Hence the contribution of case
2 except for “u = 0 and v = 1” would be
P(S
v
[u] = v)P(S
v
[v] = v)P(j
v
+ S
v
[v] + K[v] = u),
