Boolean Functions with Maximum Algebraic Immunity Based on Properties of Punctured Reed-Muller Codes

摘要

The construction of Boolean functions with an odd number of variables and maximum algebraic immunity is studied in this paper. Starting with any function f obtained by the Carlet-Feng construction, we develop an efficient method to properly modify f in order to provide new functions having maximum algebraic immunity. This new approach, which exploits properties of the punctured Reed-Muller codes, suffices to generate a large number of new functions with maximum algebraic immunity through swapping an arbitrary number of elements between the support of f and its complement.