Construction of balanced Boolean functions with high nonlinearity,good local and global avalanche characteristics

Boolean functions possessing multiple cryptographic criteria play an important role in the design of symmetric cryptosystems. The following criteria for cryptographic Boolean functions are often considered: high nonlinearity, balancedness, strict avalanche criterion, and global avalanche characteristics. The trade-off among these criteria is a difficult problem and has attracted many researchers. In this paper, two construction methods are provided to obtain balanced Boolean functions with high nonlinearity. Besides, the constructed functions satisfy strict avalanche criterion and have good global avalanche characteristics property. The algebraic immunity of the constructed functions is also considered.     

On the security of the Feng–Liao–Yang Boolean functions with optimal algebraic immunity against fast algebraic attacks

In the past few years, algebraic attacks against stream ciphers with linear feedback function have been significantly improved. As a response to the new attacks, the notion of algebraic immunity of a Boolean function f was introduced, defined as the minimum degree of the annihilators of f and f + 1. An annihilator of f is a nonzero Boolean function g, such that fg = 0. There is an increasing interest in construction of Boolean functions that possess optimal algebraic immunity, combined with other characteristics, like balancedness, high nonlinearity, and high algebraic degree. In this paper, we investigate a recently proposed infinite class of balanced Boolean functions with optimal algebraic immunity, optimum algebraic degree and much better nonlinearity than all the previously introduced classes of Boolean functions with maximal algebraic immunity. More precisely, we study the resistance of the functions against one of the new algebraic attacks, namely the fast algebraic attacks (FAAs). Using the special characteristics of the family members, we introduce an efficient method for the evaluation of their behavior against these attacks. The new algorithm is based on the well studied Berlekamp–Massey algorithm.     

Normal Boolean functions

Dobbertin (Construction of bent functions and balanced Boolean functions with high nonlinearity, in: Fast Software Encryption, Lecture Notes in Computer Science, Vol. 1008, Springer, Berlin, 1994, pp. 61–74) introduced the normality of bent functions. His work strengthened the interest for the study of the restrictions of Boolean functions on k-dimensional flats providing the concept of k-normality. Using recent results on the decomposition of any Boolean functions with respect to some subspace, we present several formulations of k-normality. We later focus on some highly linear functions, bent functions and almost optimal functions. We point out that normality is a property for which these two classes are strongly connected. We propose several improvements for checking normality, again based on specific decompositions introduced in Canteaut et al. (IEEE Trans. Inform. Theory, 47(4) (2001) 1494), Canteaut and Charpin (IEEE Trans. Inform. Theory). As an illustration, we show that cubic bent functions of 8 variables are normal.     

On second-order nonlinearity and maximum algebraic immunity of some bent functions in \mathcal{PS}^{+}

The rth-order nonlinearity and algebraic immunity of Boolean function play a central role against several known attacks on stream and block ciphers. Since its maximum equals the covering radius of the rth-order Reed-Muller code, it also plays an important role in coding theory. The computation of exact value or high lower bound on the rth-order nonlinearity of a Boolean function is very complected/challenging problem, especially when r>1. In this article, we identify a subclass of \({\mathcal{D}}_{0}\) type bent functions constructed by modifying well known Dillon functions having sharper bound on their second-order nonlinearity. We further, identify a subclass of bent functions in \({\mathcal {PS}}^{+}\) class with maximum possible algebraic immunity. The result is proved by using the well known conjecture proposed by Tu and Deng (Des. Codes Cryptogr. 60(1):1–14, 2011). To obtain rth-order nonlinearity (r>2), that is, whole nonlinearity profile of the constructed bent functions is still an open problem.     

A systematic method of constructing Boolean functions with optimal algebraic immunity based on the generator matrix of the Reed–Muller code

Because of the recent algebraic attacks, optimal algebraic immunity is now an absolutely necessary (but not sufficient) property for Boolean functions used in stream ciphers. In this paper, we firstly determine the concrete coefficients in the linear expression of the column vectors with respect to a given basis of the generator matrix of Reed–Muller code, which is an important tool for constructing Boolean functions with optimal algebraic immunity. Secondly, as applications of the determined coefficients, we provide simpler and direct proofs for two known constructions. Further, we construct new Boolean functions on odd variables with optimal algebraic immunity based on the generator matrix of Reed–Muller code. Most notably, the new constructed functions possess the highest nonlinearity among all the constructions based on the generator matrix of Reed–Muller code, although which is not as good as the nonlinearity of Carlet–Feng function. Besides, the ability of the new constructed functions to resist fast algebraic attacks is also checked for the variable \(n=11,13\) and 15.     

Patterson-Wiedemann construction revisited

In 1983, Patterson and Wiedemann constructed Boolean functions on n=15 input variables having nonlinearity strictly greater than 2^n-1-2^(n-1)/2. Construction of Boolean functions on odd number of variables with such high nonlinearity was not known earlier and also till date no other construction method of such functions are known. We note that the Patterson-Wiedemann construction can be understood in terms of interleaved sequences as introduced by Gong in 1995 and subsequently these functions can be described as repetitions of a particular binary string. As example we elaborate the cases for n=15,21. Under this framework, we map the problem of finding Patterson-Wiedemann functions into a problem of solving a system of linear inequalities over the set of integers and provide proper reasoning about the choice of the orbits. This, in turn, reduces the search space. Similar analysis also reduces the complexity of calculating autocorrelation and generalized nonlinearity for such functions. In an attempt to understand the above construction from the group theoretic view point, we characterize the group of all GF(2)-linear transformations of GF(2^ab) which acts on PG(2,2^a).     

Maximal number of Boolean functions realized by an initial Boolean automaton with two constant states

The problem of realization of Boolean functions by initial Boolean automata with two constant states and n inputs is considered. An initial Boolean automaton with two constant states and n inputs is an initial automaton with output such that in all states the output functions are n-ary constant Boolean functions 0 or 1. The maximum cardinality of set of n-ary Boolean functions, where n > 1, realized by an initial Boolean automaton with two constant states and n inputs is obtained.     

幂函数的一些密码学性质

二元域上n数组空间上的非线性置换在分组码，杂凑函数与流密码等密码学领域中有重要应用.域GF（2n）上的幂函数提供了二元域上n数组空间上的一类非线性置换．本文着重研究幂函数的强完全性、完全性与非线性度等密码学性质．作为结果，本文证明了幂函数具有完全性；证明了具有强完全性的函数必有较高的拓扑非线性度；木文找到一类具有强完全性的幂函数；周时也定出了幂函数的代数非线性度．     

Several classes of even-variable 1-resilient rotation symmetric Boolean functions with high algebraic degree and nonlinearity

Recent research shows that the class of rotation symmetric Boolean functions is potentially rich in functions of cryptographic significance. In this paper, some classes of 2m-variable (m is an odd integer) 1-resilient rotation symmetric Boolean functions are got, whose nonlinearity and algebraic degree are studied. For the first time, we obtain 2m-variable 1-resilient rotation symmetric Boolean functions having high nonlinearity and optimal algebraic degree. In addition, we obtain a class of non-linear rotation symmetric 1-resilient function for every $n\ge 5$, and a class of quadratic rotation symmetric $(k?1)$-resilient function of $n=3k$ variables, where k is an integer.     

Estimates for the number of Boolean functions realized by an initial Boolean automaton with three constant states

The problem of realization of Boolean functions by initial Boolean automata with constant states and n inputs is considered. Such automata are those whose output function coincides with one of n-ary constant Boolean functions 0 or 1 in all states. The exact value of the maximum number of n-ary Boolean functions, where n > 1, realized by an initial Boolean automaton with three constant states and n inputs is obtained.     

Generic cryptographic weakness of k-normal Boolean functions in certain stream ciphers and cryptanalysis of grain-128

This paper considers security implications of k-normal Boolean functions when they are employed in certain stream ciphers. A generic algorithm is proposed for cryptanalysis of the considered class of stream ciphers based on a security weakness of k-normal Boolean functions. The proposed algorithm yields a framework for mounting cryptanalysis against particular stream ciphers within the considered class. Also, the proposed algorithm for cryptanalysis implies certain design guidelines for avoiding certain weak stream cipher constructions. A particular objective of this paper is security evaluation of stream cipher Grain-128 employing the developed generic algorithm. Contrary to the best known attacks against Grain-128 which provide complexity of a secret key recovery lower than exhaustive search only over a subset of secret keys which is just a fraction (up to 5%) of all possible secret keys, the cryptanalysis proposed in this paper provides significantly lower complexity than exhaustive search for any secret key. The proposed approach for cryptanalysis primarily depends on the order of normality of the employed Boolean function in Grain-128. Accordingly, in addition to the security evaluation insights of Grain-128, the results of this paper are also an evidence of the cryptographic significance of the normality criteria of Boolean functions.     

On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

Representations of Boolean functions by exclusive-OR sums (modulo 2) of pseudoproducts is studied. An ExOR-sum of pseudoproducts (ESPP) is the sum modulo 2 of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this form, and the length of a Boolean function in the class of ESPPs is defined as the minimum length of an ESPP representing this function. The Shannon function L ^ESPP(n) of the length of Boolean functions in the class of ESPPs is considered, which equals the maximum length of a Boolean function of n variables in this class. Lower and upper bounds for the Shannon function L ^ESPP(n) are found. The upper bound is proved by using an algorithm which can be applied to construct representations by ExOR-sums of pseudoproducts for particular Boolean functions.     

Asymptotic Behavior of Perturbations of Symmetric Functions

In this paper we consider perturbations of symmetric Boolean functions \({{\sigma_{n,k_1}} +\ldots+{\sigma_{n,k_s}}}\) in n-variable and degree k _s . We compute the asymptotic behavior of Boolean functions of the type $${\sigma_{n,k_1}} +\ldots+{\sigma_{n,k_s}} +F(X_1, . . . , X_j)$$ for j fixed. In particular, we characterize all the Boolean functions of the type $${\sigma_{n,k_1}} +\ldots+{\sigma_{n,k_s}} +F(X_1, . . . , X_j)$$ that are asymptotic balanced. We also present an algorithm that computes the asymptotic behavior of a family of Boolean functions from one member of the family. Finally, as a byproduct of our results, we provide a relation between the parity of families of sums of binomial coefficients.     

Boolean functions with maximum algebraic immunity: further extensions of the Carlet–Feng construction

The algebraic immunity of Boolean functions is studied in this paper. More precisely, having the prominent Carlet–Feng construction as a starting point, we propose a new method to construct a large number of functions with maximum algebraic immunity. The new method is based on deriving new properties of minimal codewords of the punctured Reed–Muller code \(\mathrm{RM}^{\star }(\lfloor \frac{n-1}{2}\rfloor ,n)\) for any n, allowing—if n is odd—for efficiently generating large classes of new functions that cannot be obtained by other known constructions. It is shown that high nonlinearity, as well as good behavior against fast algebraic attacks, is also attainable.     

Further properties of several classes of Boolean functions with optimum algebraic immunity

Based on a method proposed by the first author, several classes of balanced Boolean functions with optimum algebraic immunity are constructed, and they have nonlinearities significantly larger than the previously best known nonlinearity of functions with optimal algebraic immunity. By choosing suitable parameters, the constructed n-variable functions have nonlinearity for even for odd n, where Δ(n) is a function increasing rapidly with n. The algebraic degrees of some constructed functions are also discussed.      

A refinement of Cusick-Cheon bound for the second order binary Reed-Muller code

We prove a stronger form of the conjectured Cusick-Cheon lower bound for the number of quadratic balanced Boolean functions. We also prove various asymptotic results involving B(k,m), the number of balanced Boolean functions of degree ≤k in m variables, in the case k=2. Finally, we connect our results for k=2 with the (still unproved) conjectures of Cusick-Cheon for the functions B(k,m) with k>2.     

Boolean functions with MacWilliams duality

We introduce a new class of Boolean functions for which the MacWilliams duality holds, called MacWilliams-dual functions, by considering a dual notion on Boolean functions. By using the MacWilliams duality, we prove the Gleason-type theorem on MacWilliams-dual functions. We show that a collection of MacWilliams-dual functions contains all the bent functions and all formally self-dual functions. We also obtain the Pless power moments for MacWilliams-dual functions. Furthermore, as an application, we prove the nonexistence of bent functions in 2n variables with minimum degree n?k for any nonnegative integer k and n ≥ N with some positive integer N under a certain condition.     

Boolean Functions with Five Controllable Cryptographic Properties

The strict avalanche criterion (SAC) was introduced by Webster and Tavares [10] in a study of cryptographic design criteria. This is an indicator for local property. In order to improve the global analysis of cryptographically strong functions, Zhang and Zheng [11] introduced the global avalanche characteristics (GAC). The sum-of-squares indicator related to the GAC is defined as _f = _{v f} ²(v), where _f (v)=x (–1) ^f (x)f(x v). In this paper, we give a few methods to construct Boolean functions controlling five good cryptographic properties, namely balancedness, good local and GAC, high nonlinearity and high algebraic degree. We improve upon the results of Stanica [8] and Zhang and Zheng [11].     

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ^ESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that L ^ESPP(n) = ? (2 ⁿ /n ²). The quantity L ^ESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions.     

Upper and Lower Bounds on Maximum Nonlinearity of n-input m-output Boolean Function

The paper presents lower and upper bounds on the maximumnonlinearity for an n-input m-output Booleanfunction. We show a systematic construction method for a highlynonlinear Boolean function based on binary linear codes whichcontain the first order Reed-Muller code as a subcode. We alsopresent a method to prove the nonexistence of some nonlinearBoolean functions by using nonexistence results on binary linearcodes. Such construction and nonexistence results can be regardedas lower and upper bounds on the maximum nonlinearity. For somen and m, these bounds are tighter than theconventional bounds. The techniques employed here indicate astrong connection between binary linear codes and nonlinear n-input m-output Boolean functions.