S-boxes having large number of linearly independent multivariate biaffine or quadratic equations may be susceptible to certain kinds of algebraic attacks. In a 2009 IEEE-IT paper, Nawaz et al. provided a polynomial time algorithm to compute the number of such equations for finding S-boxes based on power mapping. Finding actual equations in polynomial time was still open. In this paper, techniques for finding a maximal set of linearly independent biaffine and quadratic equations are developed for S-boxes based on power mappings. Two algorithms to calculate the biaffine and quadratic equations for any (n, n) S-box based on power mapping are presented. The time complexity of both the algorithms is O(n6).

We study the relationship between the Walsh transform and the algebraic normal form (ANF) of a Boolean function. In the first part of the paper, we obtain a formula for the Walsh transform at a certain point in terms of parameters derived from the algebraic normal form. We use previous results by Carlet and Guillot to obtain an explicit expression for the Walsh transform at a point in terms of parameters derived from the ANF. The second part of the paper is devoted to simplify this formula and develop an algorithm to evaluate it. This algorithm can be applied in situations where it is practically impossible to use the fast Walsh transform algorithm. Experimental results show that under certain conditions it is possible to execute our algorithm to evaluate the Walsh transform (at a small set of points) of functions on a few scores of variables having a few hundred terms in the algebraic normal form.

The algebraic immunity of an S-box depends on the number and type of linearly independent multivariate equations it satisfies. In this paper, techniques are developed to find the number of linearly independent, multivariate, bi-affine, and quadratic equations for S-boxes based on power mappings. These techniques can be used to prove the exact number of equations for any class of power mappings. Two algorithms to calculate the number of bi-affine and quadratic equations for any$(n,n)$S-box based on power mapping are also presented. The time complexity of both algorithms is only$O(n^2)$. To design algebraically immune S-boxes, four new classes of S-boxes that guarantee zero bi-affine equations and one class of S-boxes that guarantees zero quadratic equations are presented. The algebraic immunity of power mappings based on Kasami, Niho, Dobbertin, Gold, Welch, and inverse exponents are discussed along with other cryptographic properties and several cryptographically strong S-boxes are identified. It is conjectured that a known Kasami-like highly nonlinear power mapping is differentially$4$-uniform. Finally, an open problem to find an$(n,n)$bijective nonlinear S-box with more than$5n$quadratic equations is solved.

Recently, algebraic attacks have received a lot of attention in the cryptographic literature. It has been observed that a Boolean function f used as a cryptographic primitive, and interpreted as a multivariate polynomial over F/sub 2/, should not have low degree multiples obtained by multiplication with low degree nonzero functions. In this paper, we show that a Boolean function having low nonlinearity is (also) weak against algebraic attacks, and we extend this result to higher order nonlinearities. Next, we present enumeration results on linearly independent annihilators. We also study certain classes of highly nonlinear resilient Boolean functions for their algebraic immunity. We identify that functions having low-degree subfunctions are weak in terms of algebraic immunity, and we analyze some existing constructions from this viewpoint. Further, we present a construction method to generate Boolean functions on n variables with highest possible algebraic immunity /spl lceil/n/2/spl rceil/ (this construction, first presented at the 2005 Workshop on Fast Software Encryption (FSE 2005), has been the first one producing such functions). These functions are obtained through a doubly indexed recursive relation. We calculate their Hamming weights and deduce their nonlinearities; we show that they have very high algebraic degrees. We express them as the sums of two functions which can be obtained from simple symmetric functions by a transformation which can be implemented with an algorithm whose complexity is linear in the number of variables. We deduce a very fast way of computing the output to these functions, given their input.

We provide two new construction methods for nonlinear resilient functions. The first method is a simple modification of a construction due to Zhang and Zheng and constructs n-input, m-output resilient S-boxes with degree d>m. We prove by an application of the Griesmer bound for linear error-correcting codes that the modified Zhang-Zheng construction is superior to the previous method of Cheon in Crypto 2001. Our second construction uses a sharpened version of the Maiorana-McFarland technique to construct nonlinear resilient functions. The nonlinearity obtained by our second construction is better than previously known construction methods.

In 2001, Nyberg proved three important correlation theorems and applied them to several cryptanalytic contexts. We continue the work of Nyberg in a more theoretical direction. We consider a general functional form and obtain its Walsh transform. Two of Nyberg's correlation theorems are seen to be special cases of our general functional form. S-box lookup, addition modulo 2/sup 2k/, and X-OR are three frequently occurring operations in the design of symmetric ciphers. We consider two methods of combining these operations and in each apply our main result to obtain the Walsh transform.

We consider the problem of constructing perfect nonlinear multiple-output Boolean functions satisfying higher order strict avalanche criteria (SAC). Our first construction is an infinite family of 2-output perfect nonlinear functions satisfying higher order SAC. This construction is achieved using the theory of bilinear forms and symplectic matrices. Next we build on a known connection between 1-factorization of a complete graph and SAC to construct more examples of 2- and 3-output perfect nonlinear functions. In certain cases, the constructed S-boxes have optimal tradeoff between the following parameters: numbers of input and output variables, nonlinearity, and order of SAC. In case the number of input variables is odd, we modify the construction for perfect nonlinear S-boxes to obtain a construction for maximally nonlinear S-boxes satisfying higher order SAC. Our constructions present the first examples of perfect nonlinear and maximally nonlinear multiple-output S-boxes satisfying higher order SAC. Finally, we present a simple method for improving the degree of the constructed functions with a small tradeoff in nonlinearity and the SAC property. This yields functions which have possible applications in the design of block ciphers.