Cryptography Reference
In-Depth Information
Thus, the probability contribution of this part is
v v
N
N−v−1
N−1
N −1
N
N −1
N
= v
N
N −1
N
.
Case II: For some τ, 1 ≤τ ≤ v, it is not touched by any of {j 1 ,j 2 ,...,j τ−1
};
after that it is touched for the first time by j τ = v in round τ and hence is
moved to index τ−1; and it is not touched by any one of the subsequent
(N −τ) many j values. The probability contribution of this part is
v
τ−1 1
N
N−τ
N−1
N −1
N
N −1
N
= v
N
N −1
N
.
τ=1
Adding the above two contributions, we get the result.
Using similar arguments one could compute the probability that a value is
touched exactly twice, thrice and in general x times, during the KSA. However,
the computation would be tedious and complicated for x > 1. Next, let us
look into a more natural measure of this asymmetric behavior, namely, the
expected number of times each value in the permutation is touched during the
KSA. This is computed in the following theorem.
Theorem 3.3.2. For 0 ≤ v ≤N −1, the expected number of times a value v
in the permutation is touched by the indices i,j during the KSA is given by
v
2N −v
N
N −1
N
E v = 1 +
.
Proof: Let x v,y = 1, if the value v is touched by the indices i,j in round
y + 1 of the KSA (i.e., when i = y); otherwise, let x v,y = 0, 0 ≤ v ≤ N − 1,
0 ≤y ≤ N−1. Then the number of times v is touched by i,j during the KSA
is given by
N−1
X v =
x v,y .
y=0
1
In any round y + 1, any value v is touched by j with a probability
N . To
this, we need to add the probability of v being touched by i, in order to find
P(x v,y = 1). Now, v is touched by the index i in round y + 1, if and only if
S y [y] = v. We consider three possible ways in which S y [y] can become v.
Case I: Consider y < v. Initially, the value v was situated in index v. In
order for v to move from index v to index y < v, either v has to be
touched by i and y has to be touched by j, or vice versa, during the first
y rounds. However, this is not possible, since neither the index y nor
the index v has been touched by the index i so far. Thus,
P(S y [y] = v) = 0.
Search WWH ::




Custom Search