Constructions Of Resilient Boolean Functions With Maximal Degree

In 1984, Siegenthaler proposed the concept of correlation immunity, and proved that an n input 1 output, m-resilient (balanced m-th order correlation-immune) Boolean function with algebraic degree d satisfies the inequality m + d ≤ n - 1. After that the construction of resilient Boolean functions becomes an important direction of the research of Boolean function. Maitra and Sarkar provided a recursive construction method to construct m-resilient Boolean functions of n variables with high nonlinearity and algebraic degree n-m-1 in 1999, but the number of the functions constructed by the method is too limited. In this paper, first we define a kind of transformation on the sequences of Boolean functions, and then analyze the changes of nonlinearity, algebraic degree and balancedness of Boolean functions under the transformation. As a result, we provide a new recursive construction method which can construct m-resilient Boolean functions of n variables with high nonlinearity and algebraic degree n-m-1. Since there are a large number of transformations that can be used in this method, compared with the original one, our method can construct more functions, which have the same characteristics as the ones constructed by the original method.