Cryptography Reference
In-Depth Information
success rate of 99%. This attack can further be improved in order to break the full DES
by using 2
43
known plaintexts (see Ref. [125]).
4.3
Classical Security Strengthening
4.3.1
Nonlinearities
In order to measure the nonlinearity of a function
f
we define
DP
f
(
a
,
=
+
=
+
b
)
Pr[
f
(
X
a
)
f
(
X
)
b
]
DP
f
max
=
DP
f
(
a
max
a
=
0
,
b
,
b
)
LP
f
(
a
1)
2
,
b
)
=
(2 Pr[
a
·
X
=
b
·
f
(
X
)]
−
LP
f
max
=
0
LP
f
(
a
max
a
,
b
)
,
b
=
where the probabilities hold over the uniform distribution of the random variable
X
.
The nonlinearity for differential cryptanalysis corresponds to DP, and the nonlinear-
ity for linear cryptanalysis corresponds to LP. DP
f
(
a
,
b
) actually corresponds to the
b
differential characteristic for
f
.LP
f
(
a
probability of the
a
→
,
b
) corresponds to the
LP bias of the
a
·
x
⊕
b
·
f
(
x
) bit. DP and LP are connected with the discrete Fourier
transform.
p
q
p
and b
q
we have
Theorem 4.2.
If f
:
{
0
,
1
}
→{
0
,
1
}
,
for any a
∈{
0
,
1
}
∈{
0
,
1
}
2
−
p
α,β
LP
f
(
a
1)
(
a
·
α
)
+
(
b
·
β
)
DP
f
(
,
b
)
=
(
−
α, β
)
2
−
q
α,β
DP
f
(
a
1)
(
a
·
α
)
+
(
b
·
β
)
LP
f
(
,
b
)
=
(
−
α, β
)
Proof.
We first notice that
1)
(
a
·
x
)
+
(
b
·
f
(
x
))
(
−
+
1
1
a
·
x
=
b
·
f
(
x
)
=
2
thus
2
1
−
p
1
2
LP
f
(
a
,
b
)
=
1
a
·
x
=
b
·
f
(
x
)
−
x
∈{
0
,
1
}
p
2
−
p
1)
(
a
·
x
)
+
(
b
·
f
(
x
))
2
=
(
−
x
∈{
0
,
1
}
p
2
−
2
p
1)
(
a
·
(
x
⊕
y
))
+
(
b
·
(
f
(
x
)
⊕
f
(
y
)))
=
(
−
.
Search WWH ::
Custom Search