Information Technology Reference
In-Depth Information
A New Tool for Assurance of Perfect
Nonlinearity
Nuray At
andStephenD.Cohen
1
Department of Informatics, University of Bergen, PB 7803, 5020 Bergen, Norway
Nuray.At@ii.uib.no
2
Department of Mathematics, University of Glasgow, Glasgow G12 8QW, Scotland
sdc@maths.gla.ac.uk
Abstract.
Let
f
(
x
) be a mapping
f
:GF(
p
n
)
→
GF(
p
n
), where
p
is
prime and GF(
p
n
) is the finite field with
p
n
elements. A mapping
f
is
called differentially
k
-uniform if
k
is the maximum number of solutions
x ∈
GF(
p
n
)of
f
(
x
+
a
)
− f
(
x
)=
b
,where
a, b ∈
GF(
p
n
)and
a
=0.
A 1-uniform mapping is called perfect nonlinear (PN). In this paper, we
propose an approach for assurance of perfect nonlinearity which involves
simply checking a trace condition.
Keywords:
perfect nonlinear, equivalence of functions.
1
Introduction
Highly nonlinear mappings have important applications in cryptography, se-
quences, and coding theory. Let
f
(
x
) be a mapping
f
:GF(
p
n
)
GF(
p
n
),
where
p
is prime and GF(
p
n
) is the finite field with
p
n
elements. There are sev-
eral ways of measuring the nonlinearity of functions, see for example [1]. One
robust measure related to differential cryptanalysis uses derivatives. Let
N
f
(
a, b
)
denote the number of solutions
x
→
GF(
p
n
)of
f
(
x
+
a
)
∈
−
f
(
x
)=
b
,where
a, b
∈
GF(
p
n
). Define
GF(
p
n
)
,a
Δ
f
=max
{
N
f
(
a, b
)
|
a, b
∈
=0
}
.
The value
Δ
f
is called the
differential uniformity
of the mapping
f
. A mapping
is said to be differentially
k
-uniform if
Δ
f
=
k
.
For applications in cryptography and coding theory, one would like to find
functions for which
Δ
f
is small. In the binary case,
p
=2,thesolutionsof
f
(
x
+
a
)
f
(
x
)=
b
come in pairs; therefore,
Δ
f
= 2 is the smallest possible
value. If
Δ
f
= 2, the function
f
is called
almost perfect nonlinear
(APN). On
the other hand, for an odd prime
p
, there exist mappings with
Δ
f
= 1. Such
mappings are called
perfect nonlinear
(PN), also known as
planar
.
Both APN and PN functions have been investigated for many years. Recently,
there is an elicited interest on them. Few functions with small
Δ
f
,uptoequiva-
lence, are known. The monomial power mappings,
f
(
x
)=
x
d
, are the most studied
−
