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


Regular paper in IEEE Transactions on Information Theory.
To appear.


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.