Cryptography Reference
In-Depth Information
Lemma 3.1.7. Assume that the index j takes its value from Z N independently
and uniformly at random at each round of the GKSA. Then, one can always
construct functions h y (S 0 ,K), which depends only on y, the secret key bytes
and the initial permutation, such that for 0 ≤ y ≤ N −1,
N −1
N
1
N ,
P
j y+1 = h y (S 0 ,K)
=
π y +
where the probabilities π y depends only on y and N.
Proof: Consider Equation (3.1). Due to the swap in round y, we have
S y [j y ] = S y−1 [y−1]; so
y,j y ,S y [y],S y−1 [y−1],K[y],K[j y ]
.
j y+1 = u
Let h y (S 0 ,K) have the following recursive formulation.
0,0,S 0 [0],S 0 [0],K[0],K[0]
h 0 (S 0 ,K) = u
and for 1 ≤ y ≤ N −1,
y,h y−1 (S 0 ,K),S 0 [y],S 0 [y−1],K[y],K[h y−1 (S 0 ,K)]
.
h y (S 0 ,K) = u
For y ≥ 0, let E y denote the event that
j y+1 = h y (S 0 ,K).
For y ≥ 1, let A y denote the event that
u(x,j x ,S x [x],S x−1 [x−1],K[x],K[j x ])
= u(x,j x ,S 0 [x],S 0 [x−1],K[x],K[j x ])
for all x ∈ [1,y]. Let A 0 denote the trivial event S 0 [0] = S 0 [0] or
0,0,S 0 [0],S 0 [0],K[0],K[0]
0,0,S 0 [0],S 0 [0],K[0],K[0]
u
= u
,
A y stand for the comple-
which occurs with probability π 0 = P(A 0 ) = 1. Let
mentary event of A y . We have
| A y )P( A y ).
P(E y ) = P(E y
|A y )P(A y ) + P(E y
| A y ) approximately equals 1 N due to
random association. By induction on y, we will show how to construct the
the probabilities π y recursively such that P(A y ) = π y . For y ≥ 1, suppose
P(A y−1 ) = π y−1 . Now the event A y occurs, if the following two hold:
1. the event A y−1 (with probability π y−1 ) occurs, and
2. one or both of the events S y [y] = S 0 [y] (with probability ( N− N ) y ) and
S y−1 [y−1] = S 0 [y−1] (with probability ( N− N ) y−1 ) occurs, depending on
whether the form of u contains one or both of these terms respectively.
We also have P(E y
|A y ) = 1 and P(E y
Search WWH ::




Custom Search