21 November 2005 in IEEE Transactions on Information Theory
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)=/spl Sigma//sub i=1//sup (n-1)/2/c/sub i/Tr(x(2/sup i/)+1), n odd and c/sub i//spl isin/F/sub 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 c/sub 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/spl ges/7 is presented, n being the number of input variables.
7 August 2002 in IEEE Transactions on Information Theory
One well-known method of generating key stream sequences for stream ciphers is to combine the outputs of several linear-feedback shift registers (LFSR) using a combining Boolean function. Here we concentrate on the design of good combining Boolean functions. We provide resilient Boolean functions with currently best known nonlinearity. These functions were not known earlier and the issues related to their existence were posed as open questions in the literature. Some of the functions we construct here achieve the provable upper bound on nonlinearity for resilient Boolean functions. Our technique interlinks mathematical results with classical computer search.
8 August 2014 in IEEE Transactions on Information Theory
A new framework concerning the construction of small-order resilient Boolean functions whose nonlinearity is strictly greater than 2 n-1 - 2 [n/2] is given. First, a generalized Maiorana-McFarland construction technique is described, which extends the current approaches by combining the usage of affine and nonlinear functions in a controllable manner. It is shown that for any given m, this technique can be used to construct a large class of n-variable (n both even and odd) m-resilient degree-optimized Boolean functions with currently best known nonlinearity. This class may also provide functions with excellent algebraic properties, measured through the resistance to (fast) algebraic attacks, if the number of n/2-variable affine subfunctions used in the construction is relatively low. Due to a potentially low hardware implementation cost, along with overall good cryptographic properties, this class of functions is an attractive candidate for the use in certain stream cipher schemes.
1 January 2014 in Finite Fields and Their Applications
1 April 2001 in Electronic Notes in Discrete Mathematics
6 February 2003 in IEEE Transactions on Information Theory
We provide a construction technique for multiple-output resilient functions F:F/sub 2//sup n//spl rarr/F/sub 2//sup m/ with high nonlinearity. The construction leads to the problem of finding a set of linear codes with a fixed minimum distance, having the property that the intersection between any two codes is the all-zero codeword only. This problem is considered, and existence results are provided. Moreover, the constructed functions obtain a nonlinearity superior to previous construction methods.