On bent and semi-bent quadratic
Boolean functions
Pascale Charpin, Enes Pasalic and Cédric Tavernier
INRIA-projet Codes, Technical University of Denmark, Thales Communication
Pascale.Charpin@inria.fr
E.Pasalic@mat.dtu.dk
cedric.tavernier@fr.thalesgroup.com
Regular paper in IEEE Transactions on Information Theory.
To appear.
Abstract
The maximum length sequences, also called m-sequences,
have received a lot of attention since the late
sixties.
In terms of LFSR synthesis they are usually generated
by certain power polynomials over finite field and in
addition
characterized by a low cross correlation and high nonlinearity.
We say that such sequence is generated by a
semi-bent function.
Some new families of such function, represented by
$f(x)=\sum_{i=1}^{\frac{n-1}{2}}c_iTr(x^{2^i+1})$,
n odd and
the c_i are binary, have recently been
introduced by Khoo, Gong and Stinson.
We first generalize their results
to even n.
We further investigate the conditions on the choice of c_i
for explicit definitions
of new infinite families
having three and four trace
terms. Also a class of nonpermutation polynomials whose
composition with a quadratic
function yields again a
quadratic semi-bent function is specified.
The treatment of semi-bent functions is then presented
in a much wider
framework. We show how bent and semi-bent functions are interlinked,
that is, the concatenation
of two suitably chosen semi-bent
functions will yield a bent function and vice versa. Finally this
approach is
generalized so that the construction of both bent and
semi-bent functions of any degree in certain range for any
n >= 7 is presented, n being the number of input variables.
Keywords :
Boolean function, m-sequence, quadratic mapping,
semi-bent function, bent function,
nonlinearity, linear permutation.