Ebook: Boolean Functions in Cryptology and Information Security

The NATO-Russia Advanced Study Institute “Boolean Functions in Cryptology and Information Security” was held in Zvenigorod (Moscow region, Russia) from September 8 to 18, 2007. The ASI was sponsored by NATO in cooperation with Lomonosov University, Moscow, and the Russian Foundation for Basic Research.

The Organizing Committee of the ASI was headed by co-directors Bart Preneel (Katholieke Universiteit Leuven and IBBT, Belgium) and Oleg Logachev (Lomonosov University, Moscow, Russia). The Information Security Institute of Lomonosov University, Moscow was responsible for the local organization of the ASI. We would like to thank many people for their cooperation, and in particular Mikhail Anokhin and Nikolay Varnovsky.

The ASI was attended by 61 participants from 11 countries. The ASI program included lectures of invited professors and talks of ASI students. We would like to acknowledge our invited professors for their contributions:

Sergey Agievich (Belarus), Valeriy Alekseev (Russia), Vladimir Anashin (Russia), Yuri Borissov (Bulgaria), Nicolas Courtois (France), Thomas Cusick (USA), Sergey Gashkov (Russia), Andrew Klapper (USA), Gohar Kyureghyan (Armenia), Philippe Langevin (France), Oleg Logachev (Russia), Subhamoy Maitra (India), Miodrag Mihaljević (Serbia), Svetla Nikova (Belgium), Valentin Nosov (Russia), Bart Preneel (Belgium), François Rodier (France), Pantelimon Stănică (Romania), Yuriy Tarannikov (Russia), Peter Wild (Australia), Jacques Wolfmann (France), Yuliang Zheng (Australia).

The proceedings of ASI are divided into three parts: lectures of invited professors, talks of students, and some open problems.

March 2008

Bart Preneel

Oleg Logachev

We study generalized regular bent functions using a representation by bent rectangles, that is, a particular class of matrices with certain rows and columns. We characterize affine transformations of bent rectangles, propose new constructions of biaffine and bilinear bent squares, study partitions of a vector space into affine planes of equal dimension, and use such partitions to build bent rectangles. We illustrate the concept of bent rectangles by examples for the Boolean case.

In this paper we introduce the notion of logical semiring and give examples of using such semirings in designing fast algorithms for discrete problems.

Loosely speaking, a T-function is a mapping from k-bit words into r-bit words such that each i-th bit of image depends only on low-order bits 0,…,i of the pre-image. For example, all arithmetic operations (addition, multiplication) are T-functions, all bitwise logical operations (XOR, AND, etc.) are T-functions. Any composition of T-functions is a T-function as well. Thus T-functions are natural computer word-oriented functions.

It turns out that T-functions are continuous (and often differentiable!) functions with respect to the so-called 2-adic distance. This enables one apply 2-adic analysis to construct wide classes of T-functions with provable cryptographic properties (long period, balance, uniform distribution, high linear complexity, etc.). We consider stream ciphers constructed out of T-functions as specific automata that could be associated to dynamical systems on the space of 2-adic integers and apply the theory of non-Archimedean dynamical systems to study important cryptographic properties of these ciphers.

Based on classification of Boolean cubic forms of seven variables given by X.D. Hou in 1996, we show how to efficiently classify the cosets of RM(1, 7) in RM(3, 7) under the action of the general affine group AGL(7, 2). At the same time the sizes of the orbits are determined. We discuss also, the correctness of our computations.

By considering a new metric, we generalize cryptographic properties of Boolean functions such as resiliency and propagation characteristics. These new definitions result in a better understanding of the properties of Boolean functions and provide a better insight in the space defined by this metric. This approach leads to the construction of “hand-made” Boolean functions, i.e., functions for which the security with respect to some specific monotone sets of inputs is considered, instead of the security with respect to all possible monotone sets with the same cardinality, as in the usual definitions. In this way, we are able to relax some trade-offs between important properties of Boolean functions. We show relations between resilient Boolean functions, linear codes, monotone span programs, and orthogonal arrays in this generalized setting.

We state several conjectures which provide good upper and lower bounds for the number of balanced Boolean functions in n variables with degree less than or equal to k. We give proofs for several special cases and give some reasons why we think that the conjectures are true. We believe that the conjectures will be very useful for further research.

The paper surveys methods of constructing bit-parallel circuits for arithmetic operations in finite fields.

A mapping f: GF(pⁿ)→GF(pⁿ) is called differentially k-uniform if k is the maximum number of solutions x∊GF(pⁿ) of f(x+a)−f(x)=b, where a,b∊GF(pⁿ) and a≠0. A 1-uniform mapping is called perfect nonlinear (PN). In this paper we discuss some problems related to the equivalence of perfect nonlinear functions, and describe a class of perfect nonlinear binomials ux^pk+1+x² in GF(p^2k). These are the first PN binomials known to us which are composed with inequivalent monomials. We show that this family of binomials is equivalent to the monomial x². We survey some of the close connections between perfect nonlinear functions and finite affine planes, in particular those which are important for equivalence proofs.

We present the strategy that we recently used to compute the complete classification of Boolean quartic forms in eight variables. Furthermore, we outline some applications of this result.

We introduce new concepts and parameters related to the problem of studying the behavior of a Boolean mapping on flats. We also prove several results relating these concepts and parameters with cryptographic properties of Boolean mappings. Moreover, the paper contains many examples.

Here we briefly survey the state of the art nonlinearity results for Boolean functions on odd number of input variables having very high nonlinearity. We outline some results on even variable Boolean functions too.

Security evaluation techniques relevant for some models of stream ciphers based on linear feedback shift registers and Boolean functions are addressed. The article points out to some recently developed advanced algebraic and correlation attacks and their implications regarding design of secure Boolean functions. The considered cryptanalytic approaches are based on appropriately decimated sample resulting into conversion of certain Boolean functions into the weaker ones.

We construct families of Latin squares over Boolean n-tuples. This construction uses representation of Latin squares by families of Boolean functions. In this connection we study a new property of Boolean functions called properness. For these families of functions we prove classifying results.

Nyberg has introduced the notion of almost perfect nonlinearity to study differential attacks on cryptosystems. Here I will give two criterion so that a function is not almost perfectly nonlinear.

In this paper we present a result towards the conjectured nonexistence of homogeneous rotation symmetric bent functions having degree >2.

In the present paper we consider correlation immune Boolean functions and related problems. We give some interesting and important results as well as open problems. Of course, we could not give in a short paper all known results. Therefore, the facts most interesting for the author were selected.

We present a description of bent functions by means of Cyclic Codes over and (preliminary report).

This paper surveys techniques for studying and constructing balanced Boolean functions that exhibit desirable nonlinear properties including high nonlinearity, good avalanche characteristics and high orders of correlation immunity. Emphasis is placed on techniques that are of combinatorial nature, especially those that utilize extensively Hadamard matrices and hypergraphs.

We present a new large family of correlation immune Boolean functions having high nonlinearity. This family includes some known classes of highly nonlinear m-resilient functions as particular cases. We state that functions of this family have a growing algebraic immunity (together with the growth of inputs). Velocity of such a growth is at least .

In this work we present a new way to construct 3-resilient Boolean functions of 9 variables with nonlinearity 240. Such function have been discovered very recently in [1] and [2] by a heuristic search. We find these functions by an exhaustive search in the class of functions symmetric under cyclic shifts of the first seven variables. The exhaustive search was reduced significantly by using of special techniques and algorithms which can be helpful in other similar problems. Also we construct some new functions that attain the upper bound on nonlinearity of higher number of variables.

Among cryptographically significant characteristics of Boolean functions used in symmetric ciphers the algebraic immunity and the nonlinearities of high orders play the important role. Some bounds on the nonlinearities of high orders of Boolean functions via its algebraic immunity were obtained in recent papers. In this paper we improve these results and obtain new tight bounds. We prove new universal tight lower bound that reduces the problem of an estimation of high order nonlinearities to the problem of the finding of dimensions of some linear spaces of Boolean functions. As simple consequences we obtain all previously known bounds in this field. For polynomials with disjoint terms we reduce the finding of dimensions of linear spaces of Boolean functions mentioned above to a simple combinatorial analysis. Finally, we prove the tight lower bound on the nonlinearity of the second order via its algebraic immunity.