Paper 2005/437

On Boolean functions with maximum algebraic immunity

Enes Pasalic

Abstract

In this paper two important issues in theory of algebraic attacks are addressed. We first provide a theoretical framework for better understanding of design rationale in construction of Boolean functions with maximum algebraic immunity. Based on these results, an iterative design of functions with maximum possible algebraic immunity is proposed. In contrast to known constructions, our method generates balanced functions of maximum degree and high nonlinearity, that is functions satisfying all main cryptographic criteria. Additionally, functions in this class have a low implementation cost due to a small number of terms in the ANF. Secondly, for a given Boolean function, a novel algorithm for deciding the existence of annihilators of small degree is presented. The algorithm utilizes the known methods in a slightly different manner which results in a significantly reduced complexity of computation.

Note: The proofs of certain results are incorrect (one subcase has not be considered) and therefore some of the main results are not valid. Unless this is repaired I find that withdrawing the paper is a best solution.