Cryptology ePrint Archive: Report 2007/444
Tight bounds between algebraic immunity and nonlinearities of high orders
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.
Category / Keywords: boolean functions
Date: received 27 Nov 2007, last revised 15 Dec 2007
Contact author: misha_msu at mail ru
Available formats: PDF | BibTeX Citation
Version: 20071215:091046 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]