Paper 2007/444

Tight bounds between algebraic immunity and nonlinearities of high orders

Lobanov Mikhail

Abstract

Among cryptographically significant characteristics of Boolean functions used in symmetric ciphers the algebraic immunity and the nonlinearities of high orders play the important role. Some bounds on the nonlinearities of high orders of Boolean functions via its algebraic immunity were obtained in recent papers. In this paper we improve these results and obtain new tight bounds. We prove new universal tight lower bound that reduces the problem of an estimation of high order nonlinearities to the problem of the finding of dimensions of some linear spaces of Boolean functions. As simple consequences we obtain all previously known bounds in this field. For polynomials with disjoint terms we reduce the finding of dimensions of linear spaces of Boolean functions mentioned above to a simple combinatorial analysis. Finally, we prove the tight lower bound on the nonlinearity of the second order via its algebraic immunity.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
boolean functions
Contact author(s)
misha_msu @ mail ru
History
2007-12-15: last of 3 revisions
2007-12-05: received
See all versions
Short URL
https://ia.cr/2007/444
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/444,
      author = {Lobanov Mikhail},
      title = {Tight bounds between algebraic immunity and nonlinearities of high orders},
      howpublished = {Cryptology ePrint Archive, Paper 2007/444},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/444}},
      url = {https://eprint.iacr.org/2007/444}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.