Paper 2006/149

A method of construction of balanced functions with optimum algebraic immunity

C. Carlet

Abstract

Because of the recent algebraic attacks, a high algebraic immunity is now an absolutely necessary (but not sufficient) property for Boolean functions used in stream ciphers. A difference of only 1 between the algebraic immunities of two functions can make a crucial difference with respect to algebraic attacks. Very few examples of (balanced) functions with high algebraic immunity have been found so far. These examples seem to be isolated and no method for obtaining such functions is known. In this paper, we introduce a general method for proving that a given function, in any number of variables, has a prescribed algebraic immunity. We deduce an algorithm for generating balanced functions in any odd number of variables, with optimum algebraic immunity. We also give an algorithm, valid for any even number of variables, for constructing (possibly) balanced functions with optimum (or, if this can be useful, with high but not optimal) algebraic immunity. We also give a new example of an infinite class of such functions. We study their Walsh transforms. To this aim, we completely characterize the Walsh transform of the majority function.

Note: We completed the paper with a method of construction of balanced functions with optimum algebraic immunity in odd numbers of variables. This method is very general and will most probably allow obtaining many functions also achieving good nonlinearity.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Boolean functions
Contact author(s)
claude carlet @ inria fr
History
2007-06-08: last of 2 revisions
2006-04-22: received
See all versions
Short URL
https://ia.cr/2006/149
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/149,
      author = {C.  Carlet},
      title = {A method of construction of balanced functions with optimum algebraic immunity},
      howpublished = {Cryptology ePrint Archive, Paper 2006/149},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/149}},
      url = {https://eprint.iacr.org/2006/149}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.