Bent Functions

In mathematics, a Boolean function f is a map from the vectorspace \(\mathbb{F}_{2}^{n}\) of all binary vectors of length n to the finite field with two elements \(\mathbb{F}_{2}\) i.e.: \(f: \mathbb{F}_{2}^{n} \rightarrow \mathbb{F}_{2}\). The vectorspace \(\mathbb{F}_{2}^{n}\) will sometimes be also endowed with the structure of field—the field \(\mathbb{F}_{2^{n}}\) (also denoted by \(\mathbb{F}_{2^{n}}\)); indeed, this field being an n-dimensional vectorspace over \(\mathbb{F}_{2}\), each of its elements can be identified with the binary vector of length n of its coordinates relative to a fixed basis. The set of all Boolean functions \(f: \mathbb{F}_{2}^{n} \rightarrow \mathbb{F}_{2}\) will be denoted by \(\mathcal{B}_{n}\). The Hamming weight \(\mathop{\mathrm{wt}}\nolimits (x)\) of a binary vector x = (x ₁, ⋯ , x _n ) is the number of its nonzero coordinates (i.e. the size of {i ∈ N | x _i ≠ 0} where N denotes the set {1, ⋯ , n}, called the support. The Hamming weight of a Boolean function f on \(\mathbb{F}_{2}^{n}\) denoted by \(\mathop{\mathrm{wt}}\nolimits (f)\), is (also) the size of the support of the function, i.e. the set \(\{x \in \mathbb{F}_{2}^{n}\vert f(x)\neq 0\}\).The Hamming distance d _H (f, g) between two functions f and g is the size of the set \(\{x \in \mathbb{F}_{2}^{n}\vert f(x)\neq g(x)\}\). Thus it equals w _H (f ⊕g).

This chapter contains some mathematical tools, results and algebraic techniques that will be employed throughout the book. We shall provide the proofs of some results that are of importance mainly because of their use in applications and state some standard results without proof. For basic algebraic concepts, we send the reader to the excellent book of R. Lidl and H. Niederreiter [14].

Stream ciphers are commonly used for encrypting and decrypting messages. Stream ciphers have several advantages which make them suitable for some applications. Most notably, they are usually faster and have a lower hardware complexity than block ciphers. They are for instance appropriate when buffering is limited, since the binary digits are individually encrypted and decrypted. In stream cipher the encryption and the decryption consist in adding bitwise the input stream and a pseudo-random sequence generated by a pseudo-random generator taking as input a secret information, the secret key. Classical tools to produce such pseudo-random sequences, that are called keystream, are Linear Feedback Registers (LFSR). Stream ciphers can use several LFSR or a single LFSR. As indicated by its name, LFSR are linear and their linear systems are governed by linear relationships between their inputs and outputs. Since linear dependencies can relatively easily be analyzed, stream ciphers designed only with LFSR would be highly insecure.

Bent functions were invented and named in 1966 by Oscar Rothaus (1927–2003) in research not published until May 1976. So the final version was published ten years later in [67] in which Rothaus presented the basic properties and a large general family of bent functions. Dillon considers bent functions as wonderful creatures. Between 1960 and 1976, two documents on bent functions were written by J. Dillon, precisely in 1972 and 1974, but they had a limited distribution; these are the first papers he wrote on this subject [32] (where he mentions however an earlier paper, [26]) and the chapter he devoted to them in his nice PhD thesis [31]. A paper also appeared in 1975, based on Dillon’s thesis [33]. In this preliminary period, several people (including the authors of [26]) mentioned by Dillon in [32] were interested in bent functions. In [67], two names are also cited by Rothaus: Lloyd Welch, the well-known specialist of codes and sequences, and Gerry Mitchell who contributed to a computer investigation.

In this chapter we focus on constructions. There are two categories of constructions of bent functions: those which build the functions from scratch (Rothaus [36] writes that such functions are “given explicitly”)—these constructions are nowadays called primary—and those, called secondary (Rothaus [36] writes “having implicit features”), which need bent functions as initial functions for building new ones (in the same or larger number of variables).

We call secondary a construction of bent functions from already known bent functions, in the same number of variables or not (while primary constructions, like Maiorana–McFarland construction, build bent functions from scratch).

In this chapter, we present large primary constructions of bent functions derived from a secondary construction due to Carlet. We’ll see different possibilities of constructions (using permutations, involutions, the linear structures etc.) whose existence is based on algebraic problems in finite fields.

This chapter deals with an important class of bent function introduced by Dillon in 1974, which was somehow abandoned for nearly 35 years before being extended by Carlet and the author. We will see that such an extension has been very fruitful in the field of bent functions.

Let E′ be a set of representatives of the cyclotomic cosets modulo 2 ^m + 1 for which each coset has the maximal size n. Let \(f_{a_{r}}\) be the function defined on \(\mathbb{F}_{2^{n}}\) by

In this subsection, we present some classical results about elliptic curves over finite fields, as well as their connections with binary Kloosterman sums.

Let n and r be two positive integers (n ≥ 1, r ≥ 1). An (n, r)-function F (that is, a function from \(\mathbb{F}_{2}^{n}\) to \(\mathbb{F}_{2}^{r}\)) being given, the component functions of F are the Boolean functions l ∘ F, where l ranges over the set of all the nonzero linear forms over \(\mathbb{F}_{2}^{r}\). Equivalently, they are the linear combinations of a non-null number of their coordinate functions, that is, the functions of the form \(v \cdot F,v \in \mathbb{F}_{2}^{r}\setminus \{0\}\), where “⋅ ” denotes the usual inner product in \(\mathbb{F}_{2}^{r}\) (or any other inner product). The vector spaces \(\mathbb{F}_{2}^{n}\) and \(\mathbb{F}_{2}^{r}\) can be identified, if necessary, with the Galois fields \(\mathbb{F}_{2^{n}}\) and \(\mathbb{F}_{2^{r}}\) of orders 2 ⁿ and 2 ^r respectively. Hence, (n, r)-functions can be viewed as functions from \(\mathbb{F}_{2}^{n}\) to \(\mathbb{F}_{2}^{r}\) or as functions from \(\mathbb{F}_{2^{n}}\) to \(\mathbb{F}_{2^{r}}\). In the latter case, the component functions are the functions Tr₁ ^r (vF(x)). We recall some basic facts about vectorial functions.

In 1985, Kumar, Scholtz and Welch in [31] generalized the notion of Boolean bent functions to the case of functions over an arbitrary finite field. In this chapter we consider more generally bent functions in arbitrary characteristic p (where p is a prime integer).

Partial spreads and spreads play an important role in some constructions of bent functions.

Since bent functions can never be balanced (which makes them improper for a direct cryptographic use) a research on super-classes of the class of bent functions, whose elements can have high nonlinearities, but can also be balanced (and possibly, with other cryptographic properties such as resiliency) has been investigated. In the following subsections, we shall briefly present the main super-classes of bent functions introduced and studied in the literature.

The so-called plateaued functions in n variables (or r-plateaued functions) have been introduced in 1999 by Zheng and Zhang in [61] for 0 < r < n. They were firstly studied by these authors in [62, 63] and further by Carlet and Prouff in [16] as good candidates for designing cryptographic functions. The Walsh–Hadamard spectrum is a very important tool do define and design plateaued functions. An n-variable Boolean function is said to be r-plateaued if the values of its Walsh transform belong to the set \(\{0,\pm 2^{\frac{n+r} {2} }\}\) for some fixed r, 0 ≤ r ≤ n. Consequently, plateaued functions have low Hadamard transform, which provides protection against fast correlation attacks [42] and linear cryptanalysis [41]. It has been shown in [61] that plateaued functions are significant in cryptography as they possess various desirable characteristics such as high nonlinearity, resiliency, low additive autocorrelation, high algebraic degree and satisfy propagation criteria. Plateaued functions bring together various nonlinear characteristics. They include three significant classes of Boolean functions: the well-known bent functions, the near-bent functions and the semi-bent functions. More precisely, bent functions are exactly 0-plateaued functions, near-bent (also called semi-bent in odd dimension) are 1-plateaued functions and semi-bent functions are 2-plateaued functions. 0-plateaued functions and 2-plateaued functions on \(\mathbb{F}_{2^{n}}\) exist when n is even, while 1-plateaued functions on \(\mathbb{F}_{2^{n}}\) exist when n is odd.

Error correcting codes are widely studied by researchers and employed by engineers and they have long been known to have applications in computer and communication systems, data storage devices (starting from the use of Reed Solomon codes in CDs) and consumer electronics. Certain special types of functions over finite fields and vector spaces over finite fields are closely related to linear or nonlinear codes. For instance, Kerdock codes (see [25]) are constructed from bent functions. In the past decade, much progress on interplays between special functions and codes has been made. In particular, APN functions, planar functions, Dickson polynomials and q-polynomials were employed to construct linear codes with optimal or almost optimal parameters. Recently, several new approaches to constructing linear codes, with special types of functions were proposed, and a lot of linear codes with excellent parameters were obtained; in particular, the constructions with few weights from special functions. Such codes have applications in secret sharing [1, 6, 16, 17, 31] authentication codes [14], association schemes [2], and strongly regular graphs [3]. Interesting two-weight and three-weight codes have been obtained in several papers. A non-exhaustive list is [7, 8, 12, 13, 15‐18, 21, 24, 27, 29, 30, 32, 33] and [11].