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.

Metadata
Available format(s)
-- withdrawn --
Publication info
Published elsewhere. Unknown where it was published
Keywords
Algebraic attacksAlgebraic ImmunityAnnihilatorsStream ciphers
Contact author(s)
enespasalic @ yahoo se
History
2005-12-06: withdrawn
2005-11-30: received
See all versions
Short URL
https://ia.cr/2005/437
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.