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.     

Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity

Recent research shows that the class of rotation symmetric Boolean functions is potentially rich in functions of cryptographic significance. In this paper, based on the knowledge of compositions of an integer, we present two new kinds of construction of rotation symmetric Boolean functions having optimal algebraic immunity on either odd variables or even variables. Our new functions are of much better nonlinearity than all the existing theoretical constructions of rotation symmetric Boolean functions with optimal algebraic immunity. Further, the algebraic degree of our rotation symmetric Boolean functions are also high enough.     

Improving the high order nonlinearity lower bound for Boolean functions with given algebraic immunity

Algebraic immunity is a recently introduced cryptographic parameter for Boolean functions used in stream ciphers. If pAI(f) and pAI(f⊕1) are the minimum degree of all annihilators of f and f⊕1 respectively, the algebraic immunity AI(f) is defined as the minimum of the two values. Several relations between the new parameter and old ones, like the degree, the r-th order nonlinearity and the weight of the Boolean function, have been proposed over the last few years.In this paper, we improve the existing lower bounds of the r-th order nonlinearity of a Boolean function f with given algebraic immunity. More precisely, we introduce the notion of complementary algebraic immunity defined as the maximum of pAI(f) and pAI(f⊕1). The value of can be computed as part of the calculation of AI(f), with no extra computational cost. We show that by taking advantage of all the available information from the computation of AI(f), that is both AI(f) and , the bound is tighter than all known lower bounds, where only the algebraic immunity AI(f) is used.     

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.     

On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2

We improve parts of the results of [T. W. Cusick, P. Stanica, Fast evaluation, weights and nonlinearity of rotation-symmetric functions, Discrete Mathematics 258 (2002) 289-301; J. Pieprzyk, C. X. Qu, Fast hashing and rotation-symmetric functions, Journal of Universal Computer Science 5 (1) (1999) 20-31]. It is observed that the n-variable quadratic Boolean functions, for , which are homogeneous rotation symmetric, may not be affinely equivalent for fixed n and different choices of s. We show that their weights and nonlinearity are exactly characterized by the cyclic subgroup 〈s−1〉 of Z_n. If , the order of s−1, is even, the weight and nonlinearity are the same and given by . If the order is odd, it is balanced and nonlinearity is given by .     

On a method of derivation of lower bounds for the nonlinearity of Boolean functions

The calculation of the exact value of the rth order nonlinearity of a Boolean function (the power of the distance between the function and the set of functions is at most r) or the derivation of a lower bound for it is a complicated problem (especially for r > 1). Lower bounds for nonlinearities of different orders in terms of the value of algebraic immunity were obtained in a number of papers. These estimates turn out to be sufficiently strong if the value of algebraic immunity is maximum or close to maximum. In the present paper, we prove a statement that allows us to obtain fairly strong lower bounds for nonlinearities of different orders and for many functions with low algebraic immunity.     

Local properties of Boolean functions I: injectivity

This work inaugurates a cycle of papers based on the following common idea. Given a property $\text{P}\text{(f)}$ which is defined for Boolean functions $\text{?:}\text{B}{}^{\mathrm{n}}\text{→}\text{B}$, introduce and study a suitable “local” property $\text{p(?,}\text{X}\text{)}$ depending both on the function ? and on a point $\text{X}\text{∈}\text{B}{}^{\mathrm{n}}$ in such a way that for every Boolean function ?, property $\text{P(?)}$ is true if and only if $\text{p(?,}\text{X>}\text{)}$ holds for every $\text{X}\text{∈}\text{B}{}^{\mathrm{n}}$.The first article of the series deals with local injectivity, showing in particular that for n ? 1 local injectivity coincides with global injectivity, whereas for n > 1 there is no injective Boolean function (in the classical sense). Two forthcoming papers will study local isotony and applications to extremal solutions of Boolean equations.     

The selfnegadual properties of generalised quadratic Boolean functions

We define and characterise selfnegadual generalised quadratic Boolean functions by establishing a link, both to the multiplicative order of symmetric binary matrices, and also to the Hermitian self-dual ${\mathbb{F}_4}$ -linear codes. This facilitates a novel way to classify Hermitian self-dual ${\mathbb{F}_4}$ -linear codes.     

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.     

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.      

Polynomial expansions of Boolean functions with respect to nondegenerate functions

Translated from Algebra i Logika, Vol. 30, No. 6, pp. 631–637, November–December, 1991.     

Interior and exterior functions of positive Boolean functions

The interior and exterior functions of a Boolean function f were introduced in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209–231), as stability (or robustness) measures of the f. In this paper, we investigate the complexity of two problems -INTERIOR and -EXTERIOR, introduced therein. We first answer the question about the complexity of -INTERIOR left open in Makino and Ibaraki (Discrete Appl. Math. 69 (1996) 209–231); it has no polynomial total time algorithm even if is bounded by a constant, unless P=NP. However, for positive h-term DNF functions with h bounded by a constant, problems -INTERIOR and -EXTERIOR can be solved in (input) polynomial time and polynomial delay, respectively. Furthermore, for positive k-DNF functions, -INTERIOR for two cases in which k=1, and and k are both bounded by a constant, can be solved in polynomial delay and in polynomial time, respectively.     

Influences of monotone Boolean functions

Recently, Keller and Pilpel conjectured that the influence of a monotone Boolean function does not decrease if we apply to it an invertible linear transformation. Our aim in this short note is to prove this conjecture.     

Compositional complexity of Boolean functions

We define two measures, γ and c, of complexity for Boolean functions. These measures are related to issues of functional decomposition which (for continuous functions) were studied by Arnol'd, Kolmogorov, Vitu?kin and others in connection with Hilbert's 13th Problem. This perspective was first applied to Boolean functions in [1]. Our complexity measures differ from those which were considered earlier [3, 5, 6, 9, 10] and which were used by Ehrenfeucht and others to demonstrate the great complexity of most decision procedures. In contrast to other measures, both γ and c (which range between 0 and 1) have a more combinatorial flavor and it is easy to show that both of them are close to 0 for literally all “meaningful” Boolean functions of many variables. It is not trivial to prove that there exist functions for which c is close to 1, and for γ the same question is still open. The same problem for all traditional measures of complexity is easily resolved by statistical considerations.     

Exclusion sensitivity of Boolean functions

Recently the study of noise sensitivity and noise stability of Boolean functions has received considerable attention. The purpose of this paper is to extend these notions in a natural way to a different class of perturbations, namely those arising from running the symmetric exclusion process for a short amount of time. In this study, the case of monotone Boolean functions will turn out to be of particular interest. We show that for this class of functions, ordinary noise sensitivity and noise sensitivity with respect to the complete graph exclusion process are equivalent. We also show this equivalence with respect to stability. After obtaining these fairly general results, we study “exclusion sensitivity” of critical percolation in more detail with respect to medium-range dynamics. The exclusion dynamics, due to its conservative nature, is in some sense more physical than the classical i.i.d. dynamics. Interestingly, we will see that in order to obtain a precise understanding of the exclusion sensitivity of percolation, we will need to describe how typical spectral sets of percolation diffuse under the underlying exclusion process.     

Dualization of regular Boolean functions

A monotonic Boolean function is regular if its variables are naturally ordered by decreasing ‘strength’, so that shifting to the right the non-zero entries of any binary false point always yields another false point. Peled and Simeone recently published a polynomial algorithm to generate the maximal false points (MFP's) of a regular function from a list of its minimal true points (MTP's). Another efficient algorithm for this problem is presented here, based on characterization of the MFP's of a regular function in terms of its MTP's. This result is also used to derive a new upper bound on the number of MFP's of a regular function.