A systematic method of constructing Boolean functions with optimal algebraic immunity based on the generator matrix of the Reed-Muller code

摘要

Because of the recent algebraic attacks, optimal algebraic immunity is now an absolutely necessary (but not sufficient) property for Boolean functions used in stream ciphers. In this paper, we firstly determine the concrete coefficients in the linear expression of the column vectors with respect to a given basis of the generator matrix of Reed-Muller code, which is an important tool for constructing Boolean functions with optimal algebraic immunity. Secondly, as applications of the determined coefficients, we provide simpler and direct proofs for two known constructions. Further, we construct new Boolean functions on odd variables with optimal algebraic immunity based on the generator matrix of Reed-Muller code. Most notably, the new constructed functions possess the highest nonlinearity among all the constructions based on the generator matrix of Reed-Muller code, although which is not as good as the nonlinearity of Carlet-Feng function. Besides, the ability of the new constructed functions to resist fast algebraic attacks is also checked for the variable n = 11,13 and 15.