Cryptography Reference
In-Depth Information
Substituting the values of p
2
(from Lemma 3.1.12), a and b, we get
2(r−2)
2(r−1)
2
N
N −1
N
r−2
N
N −1
N
p
r
=
+
.
Putting r = N and noting the fact that
P
(S
N
[S
N
[1]] = K[0] + K[1] + 1)∧(S
N
[1] ≤ N −1)
= P(S
N
[S
N
[1]] = K[0] + K[1] + 1),
we get
P(S
N
[S
N
[1]] = K[0] + K[1] + 1)
2(N−2)
2(N−1)
2
N
N −1
N
N −2
N
N −1
N
=
+
.
The second term (≈ 0.1348 for N = 256) dominates over the negligibly small
first term (≈ 0.0011 for N = 256). So replacing
N−2
N
by (
N−1
N
)
2
in the second
term, one can write
2N
N −1
N
P(S
N
[S
N
[1]] = K[0] + K[1] + 1) ≈
So far, we have explained the non-random association between S
N
[S
N
[1]]
and f
1
. An obvious generalization of this is the association between S
N
[S
N
[y]]
and f
y
, and moving further, the association between S
N
[S
N
[S
N
[y]]] and f
y
,
for 0 ≤ y ≤ N − 1 and so on. This gives new forms of biases compared to
the previously studied biases of S
N
[y] toward f
y
. Experimental observations
show that these associations are not random (i.e., much more than
1
N
) for
initial values of y (see Figure 3.2).
Next we present the theoretical analysis of the biases of S
r
[S
r
[y]] toward
f
y
for small values of y. The results involved in the process are tedious, and
one needs to approximate certain quantities to get the closed form formula.
Lemma 3.1.15. For 0 ≤ y ≤ 31,
(S
y+1
[S
y+1
[y]] = f
y
)∧(S
y+1
[y] ≤ y)
P
0
1
y(y+1)
2
y−1
y
1
N
N −1
N
N −2
N
N −1
N
@
A
≈
y
+
.
Proof: S
y+1
[y] ≤ y means that it can take y + 1 many values 0,1,...,y.
Consider two cases:
Case I: S
y+1
[y] < y and
Case II: S
y+1
[y] = y.
