Cryptography Reference
In-Depth Information
and for “u = 0 and v = 1” it would be
P(S
1
[0] = 1)P(j
1
+ S
1
[1] + K[1] = 0)
or, equivalently,
P(S
1
[1] = 1)P(j
1
+ S
1
[1] + K[1] = 0).
Let p
u,
r
denote the probability P(S
r
[u] = v), for 1 ≤r ≤ N. The following
lemma connects the probabilities between rounds τ and r ≥ τ.
Lemma 3.2.9. Suppose, p
u,
τ
is given for any intermediate round τ, max{u,v}<
τ ≤N. Then, for τ ≤ r ≤ N, we have
r−τ
v
r−τ
N −1
N
+ (1−p
u,
τ
)
1
N
N −1
N
N −1
N
p
u,v
r
= p
u,v
τ
1−
.
Proof: After round τ (> max{u,v}), there may be two different cases:
S
τ
[u] = v and S
τ
[u] = v. Both of these can contribute to the event (S
r
[u] = v)
in the following ways.
Case I: S
τ
[u] = v and the index u is not touched by any of the subsequent
r−τ many j values. The contribution of this part is
r−τ
r−τ
N −1
N
N −1
N
= p
u,v
τ
P(S
τ
[u] = v)
.
Case II: S
τ
[u] = v and for some x in the interval [τ,r−1], S
x
[x] = v which
comes into the index u from the index x by the swap in round x+1, and
after that the index u is not touched by any of the subsequent r−1−x
many j values. So the contribution of the second part is given by
r−1
r−1−x
N − 1
N
P(S
τ
[u] = v)
P(S
x
[x] = v)P(j
x+1
= u)
.
x=τ
Suppose, the value v remains in location v after round v. By Proposi-
tion 3.2.5, this probability, i.e., P(S
v
[v] = v), is (
N−
N
)
v
. The swap in the
next round moves the value v to a random location x = j
v+1
. Thus,
P(S
v+1
[x] = v)
= P(S
v
[v] = v)P(j
v+1
= x)
v
1
N −1
N
=
N
.
For all x > v, until x is touched by the deterministic index i, i.e., until round
x + 1, v will remain randomly distributed. Hence, for all x > v,
v
1
N
N −1
N
P(S
x
[x] = v) = P(S
v+1
[x] = v) =
and
