^{1} Department of Mathematics, Technical University of Denmark^{2} unknown^{3} Department of Applied Mathematics and Computer Science, Technical University of Denmark

Abstract:

The maximum-length sequences, also called m-sequences, have received a lot of attention since the late 1960s. In terms of linear-feedback shift register (LFSR) synthesis they are usually generated by certain power polynomials over a finite field and in addition are characterized by a low cross correlation and high nonlinearity. We say that such a sequence is generated by a semi-bent function. Some new families of such function, represented by f(x) = Sigma(i=1)(n-1/2) c(i)Tr(x(2t+1)), n odd and c(i) is an element of F-2, have recently (2002) been introduced by Khoo et al. We first generalize their results to even n. We further investigate the conditions on the choice of ci 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.

Type:

Journal article

Language:

English

Published in:

Ieee Transactions on Information Theory, 2005, Vol 51, Issue 12, p. 4286-4298

Keywords:

Boolean function; bent function; nonlinearity; m-sequence; quadratic mapping; semi-bent function; linear permutation