Cryptography Reference
In-Depth Information
Hence,
P(z
ρN+2
= 0 & j
ρN
P(z
ρN+2
= 0 & j
ρN
= u)
= 0)
=
u=0
S
ρN
[2]=0
N −1
N
P(z
ρN+2
= 0 | j
ρN
= u)P(j
ρN
= u)
=
u=0
N −1
N
(N −1)
1
N
1
N
≈
1
N
−
2
1
N
3
.
=
N
2
+
By similar calculations, it can be shown that the same result holds for the
event z
ρN
= 0 as well. Thus, one can write
P(z
ρN
= 0 & j
ρN
= P(z
ρN+2
= 0 & j
ρN
= 0)
= 0)
1
N
−
2
1
N
3
.
=
N
2
+
(6.7)
By combining Equation (6.6), Lemma 6.3.5 and Equation (6.7), one can easily
see that none of z
ρN
and z
ρN+2
has bias toward 0 (of order
1
N
2
or higher).
Thus, for ρ ≥ 1,
1
N
.
P(z
ρN
= 0) = P(z
ρN+2
= 0) =
(6.8)
The main idea behind the search for a long-term distinguisher is to combine
Equation (6.6) and Lemma 6.3.5 to eliminate j
ρN
.
Theorem 6.3.6. For any integer ρ ≥ 1, assume that the permutation S
ρN
is
randomly chosen from the set of all possible permutations of {0,...,N − 1}.
Then
P(z
ρN+2
= 0 | z
ρN
= 0) ≈
1
1
N
2
.
N
+
Proof: We have
P(z
ρN+2
= 0 | z
ρN
= 0)
=
P(z
ρN+2
= 0 & z
ρN
= 0)
P(z
ρN
= 0)
= N P(z
ρN+2
= 0 & z
ρN
= 0), (using Equation (6.8))
= N P(j
ρN
= 0)P(z
ρN+2
= 0 & z
ρN
= 0 | j
ρN
= 0)
+N P(j
ρN
= 0)P(z
ρN+2
= 0 & z
ρN
= 0 | j
ρN
= 0).
= P(z
ρN+2
= 0 & z
ρN
= 0 | j
ρN
= 0)
+(N −1)P(z
ρN+2
= 0 & z
ρN
= 0 | j
ρN
= 0).
