Upper bound for algebraic immunity on a subclass of Maiorana McFarland class of bent functions
Studying algebraic immunity of Boolean functions is recently a very important research topic in cryptography. It is recently proved by Courtois and Meier that for any Boolean function of n-variable the maximum algebraic immunity is inverted right perpendicularn/2inverted left perpendicular. We found a large subclass of Maiorana McFarland bent functions on n-variable with a proven low level of algebraic immunity <= inverted right perpendicularn/4inverted left perpendicular + 2. To the best of our knowledge we provide for the first time a new upper bound for algebraic immunity for a nontrivial class of Boolean functions. We also discuss that this result has some fascinating implications. (C) 2010 Elsevier B.V. All rights reserved.
algebraic immunity bent functions cryptography nonlinearity