Cryptography Reference
In-Depth Information
Proof: First we prove item (1). Since v > u, so for any τ > v, we will
have τ > max{u,v}. Substituting τ = v + 1 in Corollary 3.2.10, we have
N−1−v
N −1
N
= p
u,v
v+1
P(S
N
[u] = v)
v
N−1−v
v+1
)
1
N −1
N
N −1
N
+(1−p
u,v
1−
N
N−1−v
N −1
N
= p
u,v
v+1
v
−
N−1
v+1
)
1
N −1
N
N −1
N
+(1−p
u,v
.
N
Now, from Lemma 3.2.7, we get
v−u
v
−
1
N
2
2v−u−1
1
N
N −1
N
1
N
N −1
N
N −1
N
p
u,v
v+1
=
+
,
except for “u = 0 and v = 1”. Also, Lemma 3.2.4 gives
=
2(N −1)
N
2
p
0,1
2
.
Substituting these values of p
u,v
v+1
, one can get the result.
Now let us prove item (2). Here we have u≥ v. So for any τ > u, we will
have τ > max{u,v}. Substituting τ = u + 1 in Corollary 3.2.10, we have
N−1−u
N −1
N
= p
u,v
u+1
P(S
N
[u] = v)
1−
v
N−1−u
u+1
)
1
N −1
N
N −1
N
+(1−p
u,v
.
N
As p
u,v
1
N
(see the proof of Proposition 3.2.6), substi-
tuting this in the above expression, we get
u+1
= P(S
u+1
[u] = v) =
N−1−u
1
N
N −1
N
P(S
N
[u] = v)
=
v
N−1−u
1−
1
N
1
N
N −1
N
N −1
N
+
1−
N−1−u
v+1
1
N
N −1
N
1
N
N −1
N
=
+
N+v−u
−
1
N
N −1
N
.
