Maximal values of generalized algebraic immunity
The notion of algebraic immunity of Boolean functions has been generalized in several ways to vector-valued functions and/or over arbitrary finite fields and reasonable upper bounds for such generalized algebraic immunities has been proved in Armknecht and Krause (Proceedings of ICALP 2006, LNCS, vol. 4052, pp 180-191, 2006), Ars and Faugere (Algebraic immunity of functions over finite fields, INRIA, No report 5532, 2005) and Batten (Canteaut, Viswanathan (eds.) Progress in Cryptology-INDOCRYPT 2004, LNCS, vol. 3348, pp 84-91, 2004). In this paper we show that the upper bounds can be reached as the maximal values of algebraic immunities for most of generalizations by using properties of Reed-Muller codes.
algebraic immunity finite field reed-muller codes cryptography