Theory of 2-rotation symmetric cubic Boolean functions
A Boolean function in \(n\) variables is \(2\)-rotation symmetric if it is invariant under even powers of the cyclic permutation \(\rho (x_1,\ldots ,x_n)=(x_2,\ldots ,x_n,x_1)\) of the variables, but not under the first power (ordinary rotation symmetry); for brevity, we call such a function a \(2\)-function. A \(2\)-function is said to be monomial rotation symmetric (MRS) if it is generated by applying powers of \(\rho ^2\) to a single monomial. This paper develops the theory of cubic MRS \(2\)-functions in \(2n\) variables generated by a monomial \(x_1 x_r x_s\) with \(1 \)2. An exact count of the equivalence classes is given and their number is proved to be very small, in fact \(O(n^{\epsilon })\) for any \(\epsilon > 0.\) It is proved that the sequence of Hamming weights \(\{wt(2 \text {-}(1,r,s)_{2n}):~2n \ge s\}\) satisfies a linear recursion with integer coefficients. A similar result for ordinary cubic MRS functions was proved recently (papers by Bileschi, Cusick and Padgett, and by Brown and Cusick), but this paper uses a new method for the \(2\)-functions proof. Unlike the ordinary MRS function case, both the orders of the recursions for the \(2\)-functions and the precise values of the roots of the corresponding recursion polynomials can be given explicitly. Finally, a precise value for the weights of the \(2\)-functions is proved, using a 2011 formula of Cusick and Padgett. These weights are connected to powers of members of the well known Lucas sequence, and so the weights can be found without computing initial values for the recursions.
rotation symmetric boolean function hamming weight recursion affine equivalence cryptography 94c10 94a60 06e30