Bent functions. Results and applications to cryptography.

*(English)*Zbl 1372.94002
Amsterdam: Elsevier/Academic Press (ISBN 978-0-12-802318-1/pbk; 978-0-12-802555-0/ebook). xviii, 202 p. (2015).

This book provides a comprehensive overview about the current state of research on bent functions. It collects more than 125 theorems, proofs of several results obtained by the author herself are included, for all other results exact reference to the original source is given in more than 400 references. Notably the book contains also many results which originally appeared in Russian, as a consequence various approaches to the topic of bent functions are present in this book. Pointing to various directions in the research of bent functions, this book potentially will influence future research on this topic.

After basics on Boolean functions and an introduction of Boolean bent functions as maximal nonlinear functions in an even number of variables in Chapters 1 and 2, in the historical notes in Chapter 3 the author cites the famous paper of O. S. Rothaus [J. Comb. Theory, Ser. A 20, 300–305 (1976; Zbl 0336.12012)], published in 1976, as the paper in which bent functions are introduced. She mentions a.o. the work of Dillon, McFarland, and, what is less known, it is also pointed out that bent functions have been studied in the 1960s in the USSR under the name of a “minimal function” by V. A. Eliseev and O. P. Stepchenkov (whose works are still classified).

In Chapter 4 application of bent functions in cryptography, coding theory, sequence design etc. are discussed. Properties of bent functions like algebraic degree, rank, duality are reviewed in Chapter 5, and the concept of extended affine equivalence is introduced. Section 6 deals with several equivalent definitions of Boolean bent functions via combinatorial objects like Hadamard matrices, difference sets and designs, strongly regular graphs, or the less known concept of bent rectangles. One of the big open problems in this area is to estimate the number of (inequivalent) bent functions. In Chapter 8 results in this direction for bent functions with a small number of variables are summarized. Several results on the enumeration of distinct classes of bent functions in up to 8 variables are cited, the exact number of bent expressions given in [P. Langevin and G. Leander, Des. Codes Cryptography 59, No. 1–3, 193–205 (2011; Zbl 1215.94059)] is recalled. Chapters 8 and 9 are dedicated to the construction of bent functions. In Chapter 8, the famous primary constructions partial spread Maiorana-McFarland are recalled, H. Dobbertin’s construction [Lect. Notes Comput. Sci. 1008, 61–74 (1995; Zbl 0939.94563)] is presented and some secondary constructions are discussed.

Section 9 collects bent functions from the finite field \(\mathbb{F}_{2^n}\) to \(\mathbb{F}_2\) given in polynomial form as \(f(x) = tr(g(x))\), for a polynomial \(g\in\mathbb{F}_{2^n}[x]\) (where \(tr(z)\) denotes the absolute trace of \(z\in\mathbb{F}_{2^n}\)), such as the monomial bent functions referred to as Gold function, Kasami function or Canteaut-Leander and Canteaut-Charpin-Kyureghyan bent function, and bent functions with Niho exponents. Some cryptographic properties for Boolean functions like correlation immunity, resiliency and algebraic immunity are mentioned in Chapter 10. The Chapter closes with a short treatment of vectorial bent functions, almost bent functions and APN-functions including references to literature on these topics. In Chapter 11 the minimum (Hamming)-distance between bent functions is analysed (here a Boolean function in dimension \(n\) is seen as a binary vector of length \(2^n\)). Amongst others, it is pointed out that the minimum distance between bent functions is \(2^{n/2}\), and results are collected on the graph of minimal distances of bent functions, of which the vertices are the bent functions and two are connected by an edge if and only if their distance is \(2^{n/2}\).

The very interesting Chapters 12, 13, 14 analyse bent functions from a quite different perspective, namely properties are studied of the set of bent functions at a whole, seen as a subset of the set of Boolean functions in some (even) dimension \(n\).

By definition, the set of bent Boolean functions in some (even) dimension \(n\) is the set of Boolean functions at the maximal possible distance from the set of all affine functions. In Chapter 12 it is shown that vice versa the set of Boolean functions at the maximal possible distance from the set of bent functions is exactly the set of affine functions, see [N. Tokareva, Discrete Math. 312, No. 3, 666–670 (2012; Zbl 1234.94068)]. Subsets of binary vectors in some dimension with such a duality property are called metrically regular sets, hence in this chapter it is shown that the set of bent functions and the set of affine functions are metrically regular. In Chapter 13 the problem of enumerating bent functions is discussed, the known bounds are recalled and it is pointed out that there is a big gap between the best known upper and lower bounds on the number of bent functions. In the last section of this chapter, the hypothesis that every Boolean function in an even number \(n\) of variables which is of degree at most \(n/2\) can we written as the sum of two bent functions is stated. It is then pointed out that proving this hypothesis would also be a breakthrough for enumerating bent functions. Chapter 14 named ”bent decomposition problem” discusses this hypothesis, partial results are given all of which are interesting by their own, see [N. N. Tokareva, Sib. Èlektron. Mat. Izv. 11, 745–751 (2014; Zbl 1325.94143)]. Chapters 15 and 16 are on generalizations, subclasses and superclasses of Boolean bent functions, like \(p\)-ary bent functions, \(\mathbb{Z}\)-bent functions, negabent functions, rotation-symmetric bent functions, normal bent functions, and partially bent and plateaued functions. Some classes of bent functions and generalizations are looked at from a cryptographic viewpoint in Chapter 17 .

After basics on Boolean functions and an introduction of Boolean bent functions as maximal nonlinear functions in an even number of variables in Chapters 1 and 2, in the historical notes in Chapter 3 the author cites the famous paper of O. S. Rothaus [J. Comb. Theory, Ser. A 20, 300–305 (1976; Zbl 0336.12012)], published in 1976, as the paper in which bent functions are introduced. She mentions a.o. the work of Dillon, McFarland, and, what is less known, it is also pointed out that bent functions have been studied in the 1960s in the USSR under the name of a “minimal function” by V. A. Eliseev and O. P. Stepchenkov (whose works are still classified).

In Chapter 4 application of bent functions in cryptography, coding theory, sequence design etc. are discussed. Properties of bent functions like algebraic degree, rank, duality are reviewed in Chapter 5, and the concept of extended affine equivalence is introduced. Section 6 deals with several equivalent definitions of Boolean bent functions via combinatorial objects like Hadamard matrices, difference sets and designs, strongly regular graphs, or the less known concept of bent rectangles. One of the big open problems in this area is to estimate the number of (inequivalent) bent functions. In Chapter 8 results in this direction for bent functions with a small number of variables are summarized. Several results on the enumeration of distinct classes of bent functions in up to 8 variables are cited, the exact number of bent expressions given in [P. Langevin and G. Leander, Des. Codes Cryptography 59, No. 1–3, 193–205 (2011; Zbl 1215.94059)] is recalled. Chapters 8 and 9 are dedicated to the construction of bent functions. In Chapter 8, the famous primary constructions partial spread Maiorana-McFarland are recalled, H. Dobbertin’s construction [Lect. Notes Comput. Sci. 1008, 61–74 (1995; Zbl 0939.94563)] is presented and some secondary constructions are discussed.

Section 9 collects bent functions from the finite field \(\mathbb{F}_{2^n}\) to \(\mathbb{F}_2\) given in polynomial form as \(f(x) = tr(g(x))\), for a polynomial \(g\in\mathbb{F}_{2^n}[x]\) (where \(tr(z)\) denotes the absolute trace of \(z\in\mathbb{F}_{2^n}\)), such as the monomial bent functions referred to as Gold function, Kasami function or Canteaut-Leander and Canteaut-Charpin-Kyureghyan bent function, and bent functions with Niho exponents. Some cryptographic properties for Boolean functions like correlation immunity, resiliency and algebraic immunity are mentioned in Chapter 10. The Chapter closes with a short treatment of vectorial bent functions, almost bent functions and APN-functions including references to literature on these topics. In Chapter 11 the minimum (Hamming)-distance between bent functions is analysed (here a Boolean function in dimension \(n\) is seen as a binary vector of length \(2^n\)). Amongst others, it is pointed out that the minimum distance between bent functions is \(2^{n/2}\), and results are collected on the graph of minimal distances of bent functions, of which the vertices are the bent functions and two are connected by an edge if and only if their distance is \(2^{n/2}\).

The very interesting Chapters 12, 13, 14 analyse bent functions from a quite different perspective, namely properties are studied of the set of bent functions at a whole, seen as a subset of the set of Boolean functions in some (even) dimension \(n\).

By definition, the set of bent Boolean functions in some (even) dimension \(n\) is the set of Boolean functions at the maximal possible distance from the set of all affine functions. In Chapter 12 it is shown that vice versa the set of Boolean functions at the maximal possible distance from the set of bent functions is exactly the set of affine functions, see [N. Tokareva, Discrete Math. 312, No. 3, 666–670 (2012; Zbl 1234.94068)]. Subsets of binary vectors in some dimension with such a duality property are called metrically regular sets, hence in this chapter it is shown that the set of bent functions and the set of affine functions are metrically regular. In Chapter 13 the problem of enumerating bent functions is discussed, the known bounds are recalled and it is pointed out that there is a big gap between the best known upper and lower bounds on the number of bent functions. In the last section of this chapter, the hypothesis that every Boolean function in an even number \(n\) of variables which is of degree at most \(n/2\) can we written as the sum of two bent functions is stated. It is then pointed out that proving this hypothesis would also be a breakthrough for enumerating bent functions. Chapter 14 named ”bent decomposition problem” discusses this hypothesis, partial results are given all of which are interesting by their own, see [N. N. Tokareva, Sib. Èlektron. Mat. Izv. 11, 745–751 (2014; Zbl 1325.94143)]. Chapters 15 and 16 are on generalizations, subclasses and superclasses of Boolean bent functions, like \(p\)-ary bent functions, \(\mathbb{Z}\)-bent functions, negabent functions, rotation-symmetric bent functions, normal bent functions, and partially bent and plateaued functions. Some classes of bent functions and generalizations are looked at from a cryptographic viewpoint in Chapter 17 .

Reviewer: Wilfried Meidl (Linz)

##### MSC:

94-02 | Research exposition (monographs, survey articles) pertaining to information and communication theory |

94A60 | Cryptography |

94D10 | Boolean functions |

06E30 | Boolean functions |