Construction of balanced even-variable Boolean functions with optimal algebraic immunity
Sihong Su · International Journal of Computer Mathematics · 2014
Given a positive integer n, let k=⌈n/2⌉−1 and s=∑i=0kni. The generator matrix G(k,n)s×2n of the kth-order Reed–Muller code RM(k,n) is an important tool in the study of Boolean functions' algebraic immunity. In this paper, choosing the last s column vectors in G(k,n) as a basis of the vector space F2s, we study the values of the coefficients in the linear expressions of G(k,n)'s column vectors over this basis. As an application, we present a new construction of balanced even-variable Boolean functions on F2n with optimal algebraic immunity by modifying the outputs of majority function. The nonlinearities of these constructed functions are also determined.