Boolean functions in coding theory and cryptology. With a foreword by V. A. Sadovnichij.
(Булевы функции в теории кодирования и криптологии.)

*(Russian)*Zbl 1110.94001
Informatsionnaya Bezopastnost’: Kriptografiya. Moscow: Moskovskiĭ Tsentr Nepreryvnogo Matematicheskogo Obrazovaniya (ISBN 5-94057-117-4). 470 p. (2004).

This comprehensive book gives a systematic exposition of cryptographic applications of the theory of Boolean functions, the only exceptions being complexity theory and solutions to systems of Boolean equations. Several of the cryptographic problems considered here are related to the encoding and decoding of Reed-Muller error-correcting codes, which are treated as well.

The book is based on the materials of courses delivered by the authors at the Moscow State University for the students of the Faculty of Mechanics and Mathematics and the Faculty of Computational Mathematics and Cybernetics, specializing in Information Security. New results obtained by the authors recently, as a part of work at the Laboratory of Mathematical Problems of Cryptography in the Moscow State University, have also been included in the monograph. The text is most valuable for high level undergraduate courses and courses for postgraduate students. It will be also useful and can be recommended as a reference for advanced specialists working on coding, cryptography and information security.

Although the exposition is self-contained and includes concise preliminaries, the text assumes familiarity with university courses on linear algebra, group theory, finite fields and polynomial theory, combinatorics, discrete mathematics and basic notions of probability theory. The following book could have been also included on the recommended reading and reference list: [R. Lidl and G. F. Pilz, Applied abstract algebra, Second edition, Springer, New York (1998; Zbl 0891.00003)]. Let us also recommend the more recent book by I. E. Shparlinski [Finite fields: theory and computation, Kluwer Acad. Publ., Dordrecht (1999; Zbl 0967.11052)], and the newer edition of [R. Lidl and H. Niederreiter, Finite fields, Second edition, Cambridge Univ. Press, Cambridge (1997; Zbl 0866.11069)] and [R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, Revision of the 1986 first edition, Cambridge Univ. Press, Cambridge (1994; Zbl 0820.11072)].

The monograph has nine chapters outlined as follows:

Chapter 1. Arithmetic of finite fields and polynomials. 1.1. Algebraic fundamentals. 1.2. The structure of finite fields. 1.3. Polynomials over finite fields. Comments to Chapter 1.

Chapter 2. Boolean functions. 2.1. Main concepts and definitions. 2.2. Numerical and metric characteristics. 2.3. Autocorrelation and mutual correlation. 2.4. The group algebra of Boolean functions. 2.5. The cryptographic properties of Boolean functions and mappings. 2.6. The covering sequences of Boolean functions. Comments to Chapter 2.

Chapter 3. Classification of Boolean functions. 3.1. The group equivalence of mappings. Polya’s theorem. 3.2. The classification of Boolean functions with five variables. 3.3. The classification of quadratic Boolean functions. 3.4. The classification of homogeneous cubic forms with eight variables. 3.5. RM-equivalence of Boolean functions. Comments to Chapter 3.

Chapter 4. Linear codes over \(F_2\). 4.1. Main properties of linear block codes. 4.2. The problem of decoding. 4.3. Cyclic codes. 4.4. Some classes of primitive cyclic codes. Comments to Chapter 4.

Chapter 5. Reed-Muller codes. 5.1. General properties of Reed-Muller codes. 5.2. The decoding algorithms of Reed. 5.3. Reed-Muller codes of first order and related codes. 5.4. Reed-Muller codes of second order and related codes. 5.5. The classification of Boolean functions and Reed-Muller codes of third order. Comments to Chapter 5.

Chapter 6. Nonlinearity. 6.1. Nonlinearity as a measure of cryptographic quality. 6.2. Maximally-nonlinear (bent-) functions and their properties. 6.3. Some classes of maximally-nonlinear (bent-) functions. 6.4. Partial maximally-nonlinear (bent-) functions and their properties. Special functions and partially defined m.-n.- (bent-) functions. 6.6. Hyper-bent-functions. 6.7. Biorthogonal bases. Comments to Chapter 6.

Chapter 7. Correlation immunity and stability. 7.1. Main definitions and properties. 7.2. The inheritance of properties under restrictions of Boolean functions. 7.3. General methods for constructing correlation-immune functions and stable mappings. 7.4. Nonlinearity of correlation-immune functions and stable mappings. 7.5. Constructing stable Boolean functions with valuable cryptographic properties. 7.6. Covering sequences of correlation-immune and stable functions. 7.7. The quadratic stable Boolean functions of maximal order. Comments to Chapter 7.

Chapter 8. Codes, Boolean mappings and cryptographic properties. 8.1. Almost perfect nonlinear and nearly bent-mappings. 8.2. Coding theory approach to the study of APN- and AB-mappings. 8.3. Cyclic codes and Boolean mappings. 8.3. Avalanche criteria and propagation criteria. 8.5. Constructing Boolean functions satisfying the propagation criterion of degree \(k\) and order \(t\). 8.6. Global avalanche characterizations of Boolean functions. Comments to Chapter 8.

Chapter 9. Elements of cryptographic analysis. 9.1. The Berlekamp-Massey algorithm. Linear complexity. 9.2. Principles of statistical method for cryptanalysis of block ciphers. 9.3. The principles of correlation cryptanalysis method. 9.4. The principles of linear cryptanalysis method. 9.5. The principles of difference (differential) cryptanalysis method. 9.6. The bans of Boolean functions. Comments to Chapter 9.

A few important known results are formulated as exercises. The book also contains a number of known open problems that can form starting points and basis for future investigations.

The book is based on the materials of courses delivered by the authors at the Moscow State University for the students of the Faculty of Mechanics and Mathematics and the Faculty of Computational Mathematics and Cybernetics, specializing in Information Security. New results obtained by the authors recently, as a part of work at the Laboratory of Mathematical Problems of Cryptography in the Moscow State University, have also been included in the monograph. The text is most valuable for high level undergraduate courses and courses for postgraduate students. It will be also useful and can be recommended as a reference for advanced specialists working on coding, cryptography and information security.

Although the exposition is self-contained and includes concise preliminaries, the text assumes familiarity with university courses on linear algebra, group theory, finite fields and polynomial theory, combinatorics, discrete mathematics and basic notions of probability theory. The following book could have been also included on the recommended reading and reference list: [R. Lidl and G. F. Pilz, Applied abstract algebra, Second edition, Springer, New York (1998; Zbl 0891.00003)]. Let us also recommend the more recent book by I. E. Shparlinski [Finite fields: theory and computation, Kluwer Acad. Publ., Dordrecht (1999; Zbl 0967.11052)], and the newer edition of [R. Lidl and H. Niederreiter, Finite fields, Second edition, Cambridge Univ. Press, Cambridge (1997; Zbl 0866.11069)] and [R. Lidl and H. Niederreiter, Introduction to finite fields and their applications, Revision of the 1986 first edition, Cambridge Univ. Press, Cambridge (1994; Zbl 0820.11072)].

The monograph has nine chapters outlined as follows:

Chapter 1. Arithmetic of finite fields and polynomials. 1.1. Algebraic fundamentals. 1.2. The structure of finite fields. 1.3. Polynomials over finite fields. Comments to Chapter 1.

Chapter 2. Boolean functions. 2.1. Main concepts and definitions. 2.2. Numerical and metric characteristics. 2.3. Autocorrelation and mutual correlation. 2.4. The group algebra of Boolean functions. 2.5. The cryptographic properties of Boolean functions and mappings. 2.6. The covering sequences of Boolean functions. Comments to Chapter 2.

Chapter 3. Classification of Boolean functions. 3.1. The group equivalence of mappings. Polya’s theorem. 3.2. The classification of Boolean functions with five variables. 3.3. The classification of quadratic Boolean functions. 3.4. The classification of homogeneous cubic forms with eight variables. 3.5. RM-equivalence of Boolean functions. Comments to Chapter 3.

Chapter 4. Linear codes over \(F_2\). 4.1. Main properties of linear block codes. 4.2. The problem of decoding. 4.3. Cyclic codes. 4.4. Some classes of primitive cyclic codes. Comments to Chapter 4.

Chapter 5. Reed-Muller codes. 5.1. General properties of Reed-Muller codes. 5.2. The decoding algorithms of Reed. 5.3. Reed-Muller codes of first order and related codes. 5.4. Reed-Muller codes of second order and related codes. 5.5. The classification of Boolean functions and Reed-Muller codes of third order. Comments to Chapter 5.

Chapter 6. Nonlinearity. 6.1. Nonlinearity as a measure of cryptographic quality. 6.2. Maximally-nonlinear (bent-) functions and their properties. 6.3. Some classes of maximally-nonlinear (bent-) functions. 6.4. Partial maximally-nonlinear (bent-) functions and their properties. Special functions and partially defined m.-n.- (bent-) functions. 6.6. Hyper-bent-functions. 6.7. Biorthogonal bases. Comments to Chapter 6.

Chapter 7. Correlation immunity and stability. 7.1. Main definitions and properties. 7.2. The inheritance of properties under restrictions of Boolean functions. 7.3. General methods for constructing correlation-immune functions and stable mappings. 7.4. Nonlinearity of correlation-immune functions and stable mappings. 7.5. Constructing stable Boolean functions with valuable cryptographic properties. 7.6. Covering sequences of correlation-immune and stable functions. 7.7. The quadratic stable Boolean functions of maximal order. Comments to Chapter 7.

Chapter 8. Codes, Boolean mappings and cryptographic properties. 8.1. Almost perfect nonlinear and nearly bent-mappings. 8.2. Coding theory approach to the study of APN- and AB-mappings. 8.3. Cyclic codes and Boolean mappings. 8.3. Avalanche criteria and propagation criteria. 8.5. Constructing Boolean functions satisfying the propagation criterion of degree \(k\) and order \(t\). 8.6. Global avalanche characterizations of Boolean functions. Comments to Chapter 8.

Chapter 9. Elements of cryptographic analysis. 9.1. The Berlekamp-Massey algorithm. Linear complexity. 9.2. Principles of statistical method for cryptanalysis of block ciphers. 9.3. The principles of correlation cryptanalysis method. 9.4. The principles of linear cryptanalysis method. 9.5. The principles of difference (differential) cryptanalysis method. 9.6. The bans of Boolean functions. Comments to Chapter 9.

A few important known results are formulated as exercises. The book also contains a number of known open problems that can form starting points and basis for future investigations.

Reviewer: Andrei Kelarev (MR 2005g:94001)