Information Technology Reference
In-Depth Information
New Perfect Nonlinear Multinomials
over F
p
2
k
for Any Odd Prime
p
Lilya Budaghyan and Tor Helleseth
Department of Informatics
University of Bergen
PB 7803, 5020 Bergen, Norway
{Lilya.Budaghyan,Tor.Helleseth}@ii.uib.no
Abstract.
We introduce two infinite families of perfect nonlinear Dem-
bowski-Ostrom multinomials over
F
p
2
k
where
p
is any odd prime. We
prove that in general these functions are CCZ-inequivalent to previously
known PN mappings. One of these families has been constructed by
extension of a known family of APN functions over
F
2
2
k
. This shows
that known classes of APN functions over fields of even characteristic
can serve as a source for further constructions of PN mappings over
fields of odd characteristics.
Besides, we supply results indicating that these PN functions define
new commutative semifields. After the works of Dickson (1906) and Al-
bert (1952), these are the firstly found infinite families of commutative
semifields which are defined for all odd primes
p
.
Keywords:
Commutative semifield, Equivalence of functions, Perfect
nonlinear, Planar function.
1
Introduction
For any positive integer
n
and any prime
p
a function
F
from the field
F
p
n
to
itself is called
differentially
δ
-uniform
if for every
a
=0andevery
b
in
F
p
n
,
the equation
F
(
x
+
a
)
F
(
x
)=
b
admits at most
δ
solutions. Functions with
low differential uniformity are of special interest in cryptography (see [3,21]).
Differentially 1-uniform functions are called
perfect nonlinear
(PN) or
planar
.
PN functions exist only for
p
odd. For
p
even differentially 2-uniform functions,
called
almost perfect nonlinear
(APN), are those which have the lowest possible
differential uniformity.
There are several equivalence relations of functions for which differential uni-
formity is invariant. First recall that a function
F
over
F
p
n
is called
linear
if
F
(
x
)=
0
≤i<n
−
a
i
x
p
i
,
a
i
∈
F
p
n
.
A sum of a linear function and a constant is called an
ane function
.We
say that two functions
F
and
F
are
ane equivalent
(or
linear equivalent
)if