A note on the algebraic immunity of the Maiorana-McFarland class of bent functions

作者：Wang Qichun^*; Tan Chik How

来源：Information Processing Letters, 2012, 112(22): 869-871.

DOI：10.1016/j.ipl.2012.08.004

• Cryptography
• Bent function
• Algebraic immunity
• Nonlinearity

In Gupta et al. (2011)[5], the authors proved that the algebraic immunity of a subclass of Maiorana-McFarland functions is at most inverted right perpendicularn/4inverted left perpendicular + 2 and claimed that this bound is tight. The main theorem of the upper bound is correct. However, their proof is incomplete and the bound is not tight. We will prove a more general theorem of a much larger subclass of Maiorana-McFarland functions and find that its algebraic immunity cannot achieve the optimum value. However, we find an 8-variable Maiorana-McFarland function which is not in that larger subclass of Maiorana-McFarland functions achieving the optimum algebraic immunity (this is the first time that a nontrivial Maiorana-McFarland function with the optimum algebraic immunity is given). Hence, this shows that there exist the Maiorana-McFarland functions achieving the optimum algebraic immunity.

• 出版日期2012-11-30