Cryptography Reference
In-Depth Information
Further,
P(S
2
[S
2
[1]]
= K[0] + K[1] + 1∧S
2
[1] ≤ 1)
2(N −1)
N
2
2
N
1−
2(N −1)
N
2
1
N
=
+
2
N
−
4(N −1)
N
4
=
≈
2
N
.
Lemma 3.1.12 shows that after the second round (i = 1,r = 2), the event
(S
2
[S
2
[1]] = K[0] + K[1] + 1) is not a random association.
Next, we present the inductive case. Let
p
r
= P(S
r
[S
r
[1]] = K[0] + K[1] + 1∧S
r
[1] ≤r−1), for r ≥ 2.
Lemma 3.1.13. For r ≥ 3, we have
2(r−2)
N −2
N
1
N
N −2
N
N −1
N
p
r
=
p
r−1
+
.
Proof: After the (r−1)-th round is over,
p
r−1
= P(S
r−1
[S
r−1
[1]] = K[0] + K[1] + 1∧S
r−1
[1] ≤r−2).
The event
(S
r
[S
r
[1]] = K[0] + K[1] + 1)∧(S
r
[1] ≤ r−1)
can occur in two mutually exclusive and exhaustive ways:
, and
Case I:
(S
r
[S
r
[1]] = K[0] + K[1] + 1)∧(S
r
[1] ≤r−2)
(S
r
[S
r
[1]] = K[0] + K[1] + 1)∧(S
r
[1] = r−1)
Case II:
.
Let us calculate the contribution of each part separately.
In the r-th round, i = r − 1 ∈ {0,...,r − 2}. Thus, Case I occurs if we
already had
Case I.a ((S
r−1
[S
r−1
[1]] = K[0] + K[1] + 1)∧(S
r−1
[1] ≤ r−2)) and
Case I.b j
r
∈{1,r−1}.
Hence, the contribution of this part is p
r−1
(
N−
N
).
Case II occurs if after the (r−1)-th round, we have the following.
S
r−1
[r−1] = r−1,S
r−1
[1] = K[0] + K[1] + 1 and j
r
= 1,
causing a swap between the elements of S at the indices 1 and r−1.
