Algebraic immunity for cryptographically significant Boolean functions: analysis and construction

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 onzero 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 [n/2] (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. Index Terms--Algebraic attacks, annihilators, Boolean functions, nonlinearity, stream ciphers, Walsh spectrum.