On bent and semi-bent quadratic Boolean functions

P. Charpin, Enes Pasalic, C. Tavernier

    Research output: Contribution to journalJournal articleResearchpeer-review

    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.
    Original languageEnglish
    JournalIEEE Transactions on Information Theory
    Volume51
    Issue number12
    Pages (from-to)4286-4298
    ISSN0018-9448
    Publication statusPublished - 2005

    Keywords

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

    Cite this