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