Cryptology ePrint Archive: Report 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.

Category / Keywords: Algebraic attacks, Algebraic Immunity, Annihilators, Stream ciphers,

Date: received 29 Nov 2005, withdrawn 6 Dec 2005

Contact author: enespasalic at yahoo se

Available format(s): (-- withdrawn --)

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.

Version: 20051206:183106 (All versions of this report)

Short URL: ia.cr/2005/437

Discussion forum: Show discussion | Start new discussion