Cryptography Reference
In-Depth Information
Case II.a We have S
r−1
[r− 1] = r− 1, if the location r− 1 is not touched
during the rounds i = 0,...,r − 2. The probability of this is at least
(
N−1
N
)
r−1
.
Case II.b The event S
r−1
[1] = K[0] + K[1] + 1 can happen in the following
way. In the first round (when i = 0), j
1
∈{1,K[0] + K[1] + 1} so that
S
1
[1] = 1 and S
1
[K[0] + K[1] + 1] = K[0] + K[1] + 1 with probability
(
N−
N
). After this, in the second round (when i = 1), we will have
j
2
= j
1
+S
1
[1] +K[1] = K[0] +K[1] + 1, and so after the swap, S
2
[1] =
K[0] + K[1] + 1. Now, K[0] + K[1] + 1 remains in index 1 from the end
of round 2 till the end of round (r−1) (when i = r−2) with probability
(
N−1
N
)
r−3
. Thus,
r−3
N −2
N
N −1
N
P(S
r−1
[1] = K[0] + K[1] + 1) =
.
Case II.c In the r-th round (when i = r−1), j
r
becomes 1 with probability
1
N
.
Hence,
(S
r
[S
r
[1]] = K[0] + K[1] + 1)∧(S
r
[1] = r−1)
P
r−1
r−3
1
N
N −1
N
N −2
N
N −1
N
=
2(r−2)
1
N
N −2
N
N −1
N
=
.
Adding the contributions of Cases I and II, we get
2(r−2)
N −2
N
1
N
N −2
N
N −1
N
p
r
=
p
r−1
+
.
The recurrence in Lemma 3.1.13 along with the base case in Lemma 3.1.12
completely specify the probabilities p
r
for all r ∈[2,. . . ,N].
Theorem 3.1.14.
2N
N −1
N
P(S
N
[S
N
[1]] = K[0] + K[1] + 1) ≈
.
Proof: Approximating
N−2
N
by (
N−1
N
)
2
, the recurrence in Lemma 3.1.13
can be rewritten as
p
r
= ap
r−1
+ a
r−1
b,
where a = (
N−1
N
)
2
and b =
1
N
. The solution of this recurrence is given by
p
r
= a
r−2
p
2
+ (r−2)a
r−1
b,
r ≥ 2.
