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.     

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.     

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 designated-weight Boolean functions with highest algebraic immunity

Algebraic immunity has been considered as one of cryptographically significant properties for Boolean functions. In this paper, we study ∑d-1 i=0 (ni)-weight Boolean functions with algebraic immunity achiev-ing the minimum of d and n - d + 1, which is highest for the functions. We present a simpler sufficient and necessary condition for these functions to achieve highest algebraic immunity. In addition, we prove that their algebraic degrees are not less than the maximum of d and n - d + 1, and for d = n1 +2 their nonlinearities equalthe minimum of ∑d-1 i=0 (ni) and ∑ d-1 i=0 (ni). Lastly, we identify two classes of such functions, one having algebraic degree of n or n-1.     

Construction of balanced Boolean functions with high nonlinearity and good autocorrelation properties

Boolean functions with high nonlinearity and good autocorrelation properties play an important role in the design of block ciphers and stream ciphers. In this paper, we give a method to construct balanced Boolean functions of n variables, where n ≥ 10 is an even integer, satisfying strict avalanche criterion (SAC), and with high algebraic degree. Compared with the known balanced Boolean functions with SAC property, the constructed functions possess the highest nonlinearity and the best global avalanche characteristics property.     

On the affine equivalence relation between two classes of Boolean functions with optimal algebraic immunity

Recently, two classes of Boolean functions with optimal algebraic immunity have been proposed by Carlet et al. and Wang et al., respectively. Although it appears that their methods are very different, it is proved in this paper that the two classes of Boolean functions are in fact affine equivalent. Moreover, the number of affine equivalence classes of these functions is also studied.     

A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity

In this paper, a combinatorial conjecture about binary strings is proposed. Under the assumption that the proposed conjecture is correct, two classes of Boolean functions with optimal algebraic immunity can be obtained. The functions in first class are bent, and then it can be concluded that the algebraic immunity of bent functions can take all possible values except one. The functions in the second class are balanced, and they have optimal algebraic degree and the best nonlinearity up to now.     

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.     

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.      

On the maximal component algebraic immunity of vectorial Boolean functions

Under study is the component algebraic immunity of vectorial Boolean functions. We prove a theorem on the correspondence between the maximal component algebraic immunity of a function and its balancedness. Some relationship is obtained between the maximal component algebraic immunity and matrices of a special form. We construct several functions with maximal component algebraic immunity in case of few variables.     

On (2~m + 1)-variable symmetric Boolean functions with submaximum algebraic immunity 2~(m-1)

All (2m +1)-variable symmetric Boolean functions with submaximal algebraic immunity 2m-1 are described and constructed. The total number of such Boolean functions is 32 ·22m-3 +3m-2 · 24 - 2 for m≥2.     

Exact relations between nonlinearity and algebraic immunity

We sharpen some lower bounds on the higher order nonlinearity of a Boolean function in terms of the value of its algebraic immunity and obtain new tight bounds. We prove a universal tight lower bound, which enables us to reduce the problem of estimating higher order nonlinearity to finding the dimension of certain linear subspaces in the space of Boolean functions. As a simple corollary of this result, we obtain all previously known estimates in this area. For polynomials with disjoint terms, finding the dimension of those linear subspaces reduces to a simple combinatorial inspection. We prove a tight lower bound on the second order nonlinearity of a Boolean function in terms of the value of its algebraic immunity.