An involution is a permutation, such that its inverse is itself (i.e., cycle length ≤ 2). Due to this property, involutions have been used in many applications, including cryptography and coding theory. In this paper, we provide a systematic study of involutions that are defined over a finite field of characteristic 2. We characterize the involution property of several classes of polynomials and propose several constructions. Furthermore, we study the number of fixed points of involutions, which is a pertinent question related to permutations with short cycle. In this paper, we mostly have used combinatorial techniques.

In this paper we study involutions over a finite field of order 2n. We present some classes, several constructions of involutions and we study the set of their fixed points.

We provide an extensive study of the differential properties of the functionsx→x2t-1 over \BBF2n, for 1tn. We notably show that the differential spectra of these functions are determined by the number of roots of the linear polynomialsx2t+bx2+(b+1)xwherebvaries in \BBF2n. We prove a strong relationship between the differential spectra ofx→x2t-1 andx→x2s-1 fors=n-t+1. As a direct consequence, this result enlightens a connection between the differential properties of the cube function and of the inverse function. We also determine the complete differential spectra ofx→x7by means of the value of some Kloosterman sums, and ofx→x2t-1 fort∈ {[n/2], [n/2]+1,n-2}.

In this paper, we study permutation polynomials over the finite fields that have linear structures. We present some results on such a permutation which transforms a hyperplane to another hyperplane. We fully characterize the bilinear polynomial with linear structure. The most important result of this paper is to show the relation between a Maiorana-McFarland function with an affine derivative and a polynomial with a linear structure. Moreover, we highlight this result in the context of resilient functions which are based on Maiorana-McFarland construction.

Some properties of the differential spectra of power functions, i.e., monomials mappings on F2n, are investigated. We focus in particular on functions with a small differential uniformity and on some infinite families of power functions.

We study permutations over the finite fields that have linear structures. Our main result is to show the relation between a Maiorana-McFarland function with an affine derivative and a polynomial with a linear structure.

This paper is devoted to the classification of hyperbent functions, i.e., bent functions which are bent up to a primitive root change. We first exhibit an infinite class of monomial functions which are not hyperbent. It implies notably that Kloosterman sums at point 1 on F2mcannot be zero, unless m = 4. Further, we show that hyperbent functions with multiple trace terms can be described by means of Dickson polynomials.

Let K(a) be the so-called classical Kloosterman sums over F2m, where m is even. In this paper, we compute K(a) modulo 24, completing our previous results for odd m. We extensively study the links between K(a) and other exponential sums, in particular with the cubic sums. We point out (as we did for odd m) that the values K(a) are related with cosets of weight 4 of primitive narrow sense extended BCH codes of length n = 2mand minimum distance 8.

We give exact expressions for the number of coset leaders in the cosets of weight 4 of binary primitive narrow sense Bose–Chaudury–Hocquenghem (BCH) codes of length $n=2^m$ (m even) with minimum distance 8 in terms of several exponential sums, including cubic sums and Kloosterman sums. This allows us to bound the number of coset leaders in these cosets.

Based on a computer search, Anne Canteaut conjectured that the exponent $2^{2r}+2^r+1$ in ${\bf F}_{2^{6r}}$ and the exponent $(2^{r}+1)^2$ in ${\bf F}_{2^{4r}}$ yield bent monomial functions. These conjectures are proved in [A. Canteaut, P. Charpin, and G. Kyureghyan, A new class of monomial bent functions, in Proceedings of the 2006 IEEE International Symposium on Information Theory, (ISIT 06 Seattle), IEEE Press, Piscataway, NJ, 2006, pp. 903–906] and [N. G. Leander, IEEE Trans. Inform. Theory, 52 (2006), pp. 738–743]. Both exponents are of binary weight 3 and define functions from the Maiorana–McFarland class $\mathcal{M}$ of bent functions to the subfield. In this paper we show that these are the only such exponents. Our proof is based on the classification of the permutation binomials $X^{2^k+2}+ \nu X$ of finite fields of even characteristics. We also extend the result of Leander, determining all bent monomial functions with the exponent $(2^{r}+1)^2$.

This paper is devoted to the study of hyperbent functions in n variables, i.e., bent functions which are bent up to a change of primitive roots in the finite field GF(2n). Our main purpose is to obtain an explicit trace representation for some classes of hyperbent functions. We first exhibit an infinite class of monomial functions which is not hyperbent. This result indicates that Kloosterman sums on F2mcannot be zero at some points. For functions with multiple trace terms, we express their spectra by means of Dickson polynomials. We then introduce a new tool to describe these hyperbent functions. The effectiveness of this new method can be seen from the characterization of a new class of binomial hyperbent functions.

The exact expressions for the number of codewords of weight 4 in the cosets of weight 4 of binary primitive BCH codes of length n = 2m(m even) with minimum distance 8 is given in terms of several exponential sums, including cubic sums and Kloosterman sums. This provides a bound on the number of codewords of weight 4 in the cosets of weight 4 and also some limitations for possible values of Kloosterman sums over GF(2m), (m even).

We study the Boolean functions on F2En, n = 6r, of the form x rarr Tr (lambdaxd) with d = 22r+ 2r+ 1. Our main result is the characterization of those lambda for which they are bent

We investigate some open problems on almost perfect nonlinear (APN) functions over a finite field of characteristic$2$. We provide new characterizations of APN functions and of APN permutations by means of their component functions. We generalize some results of Nyberg (1994) and strengthen a conjecture on the upper bound of nonlinearity of APN functions. We also focus on the case of quadratic functions. We contribute to the current works on APN quadratic functions by proving that a large class of quadratic functions cannot be APN.

Binary primitive triple-error-correcting Bose-Chaudhuri-Hocquenghem (BCH) codes of length n=2/sup m/-1 have been the object of intensive studies for several decades. In the 1970s, their covering radius was determined in a series of papers to be /spl rho/=5. However, one problem for these codes that has been open up to now is to find their coset distribution. In this paper this problem is solved and the number of cosets of each weight in any binary primitive triple-error-correcting BCH code is determined. As a consequence this also gives the coset distribution of the extended codes of length N=2/sup m/ with minimum distance 8.

We investigate some open problems on almost perfect nonlinear (APN) functions over a finite field of characteristic 2. We provide a new characterization of APN mappings and of APN permutations by means of their component functions. We also focus on the case of quadratic functions. Most notably, we prove that a class of quadratic functions cannot be APN. Our result strengthens the conjecture that all quadratic APN functions are power functions, up to equivalence

Binary primitive triple-error-correcting BCH codes have been the object of intensive studies for several decades. In the 1970s their covering radius were determined in a series of papers to be 5. However, one problem for these codes that has been open up to now is to find their coset distribution. In this paper we solve this problem and thus determine the number of cosets of each weight in binary primitive triple-error-correcting BCH codes. As a consequence this also gives the coset distribution of the extended codes with minimal distance 8

We classify those cubic m-variable Boolean functions which are (m-4)-resilient. We prove that there are four types of such functions, depending on the structure of the support of their Walsh spectra. We are able to determine, for each type, the Walsh spectrum and, then, the nonlinearity of the corresponding functions. We also give the dimension of their linear space. This dimension equals m-k where k=3 for the first type, k=4 for the second type, k=5 for the third type, and 5/spl les/k/spl les/9 for the fourth type.

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.

In a recent paper , it was shown that the restrictions of bent functions to subspaces of codimension 1 and 2 are highly nonlinear. Here, we present an extensive study of the restrictions of bent functions to affine subspaces. We propose several methods which are mainly based on properties of the derivatives and of the dual of a given bent function. We solve an open problem due to Hou . We especially describe the connection, for a bent function, between the Fourier spectra of its restrictions and the decompositions of its dual. Most notably, we show that the Fourier spectra of the restrictions of a bent function to the subspaces of codimension 2 can be explicitly derived from the Hamming weights of the second derivatives of the dual function. The last part of the paper is devoted to some infinite classes of bent functions which cannot be decomposed into four bent functions.

We introduce a new approach for the study of weight distributions of cosets of the Reed-Muller code of order 1. Our approach is based on the method introduced by Kasami (1968), using Pless (1963) identities. By interpreting some equations, we obtain a necessary condition for a coset to have a "high" minimum weight. Most notably, we are able to distinguish such cosets which have three weights only. We then apply our results to the problem of the nonlinearity of Boolean functions. We particularly study the links between this criterion and the propagation characteristics of a function.

Golomb and Gong (1997 and 1999) considered binary sequences with the trinomial property. In this correspondence we shall show that the sets of those sequences are (quite trivially) closely connected with binary cyclic codes with codewords of weight three. This approach gives us another way to deal with trinomial property problems. After disproving one conjecture formulated by Golomb and Gong, we exhibit an infinite class of sequences which do not have the trinomial property, corresponding to binary cyclic codes of length 2/sup m/-1 with minimum distance exactly four.

We study [2m-1,2m]-binary linear codes whose weights lie between w0 and 2m-w0, where w0 takes the highest possible value. Primitive cyclic codes with two zeros whose dual satisfies this property actually correspond to almost bent power functions and to pairs of maximum-length sequences with preferred crosscorrelation. We prove that, for odd m, these codes are completely characterized by their dual distance and by their weight divisibility. Using McEliece's theorem we give some general results on the weight divisibility of duals of cyclic codes with two zeros; specifically, we exhibit some infinite families of pairs of maximum-length sequences which are not preferred.

We prove the long-standing conjecture of Welch stating that for odd n=2m+1, the power function x/sup d/ with d=2/sup m/+3 is maximally nonlinear on GF(2/sup n/) or, in other terms, that the crosscorrelation function between a binary maximum-length linear shift register sequence of degree n and a decimation of that sequence by 2/sup m/+3 takes on precisely the three values -1, -1/spl plusmn/2/sup m+1/.

We study the coset weightdistributions of the 3-error-correcting binary narrow-sense BCH-codes and of their extensions, whose lengths are, respectively, 2m-1 and 2m, m odd. We prove that all weight distributions are known as soon as those of the cosets of minimum weight 4 of the extended code are known. We point out that properties of the cosets which are orphans yield interesting properties on the other cosets. We describe the classes of cosets which are equivalent under the affine permutations. At the end we produce significant numerical results, proving that the number of distinct weight distributions of cosets increases with the length of the codes.

The extended cyclic codes of length p/sup m/, p is a prime, which are invariant under the affine-group acting on F/sub pm/, are called affine-invariant codes. Following results of Berger (1996, 1994), we present the formal expression of the permutation group of these codes. Afterwards we give several tools in order to determine effectively the group of a given code or of some infinite class of codes. We next prove, by studying some examples, that our tools are efficient. In the end, we give our main application, the permutation group of primitive BCH codes defined on any prime field.

Let B be the binary two-error-correcting BCH code of length 2/sup m/-1 and let B/spl circ/ be the extended code of B. We give formal expressions of weight distributions of the cosets of the codes B/spl circ/ only depending on m. We can then deduce the weight distributions of the cosets of B. When m is odd, it is well known that there are four distinct weight distributions for the cosets of B. So our main result is about the even case. Camion, Courteau, and Montpetit (see ibid., vol.38, no.7, p.1353, 1992) observe that for the lengths 15, 63, and 255 there are eight distinct weight distributions. We prove that this property holds for the codes B/spl circ/ and B for all even m.>

Primitive binary cyclic codes of length n=2/sup m/ are considered. A BCH code with designed distance delta is denoted B(n, delta ). A BCH code is always a narrow-sense BCH code. A codeword is identified with its locator polynomial, whose coefficients are the symmetric functions of the locators. The definition of the code by its zeros-set involves some properties for the power sums of the locators. Moreover, the symmetric functions and the power sums of the locators are related to Newton's identities. An algebraic point of view is presented in order to prove or disprove the existence of words of a given weight in a code. The principal result is the true minimum distance of some BCH codes of length 255 and 511. which were not known. The minimum weight codewords of the codes B(n2/sup h/-1) are studied. It is proved that the set of the minimum weight codewords of the BCH code B(n,2/sup m-2/-1) equals the set of the minimum weight codewords of the punctured Reed-Muller code of length n and order 2, for any m.>

The author introduces a special class of primitive BCH codes, the minimal BCH (MB) codes. It is proved that an MB code has as minimum distance its designed distance. Using the Roos bound, the author proposes a lower bound, sometimes tight, for the minimum distance of the dual of an MB code. He describes the subclass of weakly self-dual extended MB codes and then characterizes some weakly self-dual extended BCH codes. Similarly, he proves that the nontrivial extended MB code over GF(4) is the smallest extended BCH code which is not an even code. He points out that extended MB codes are principal ideals of a modular algebra.>