Fast evaluation, weights and nonlinearity of rotation-symmetric functions (Q1850065)

The paper is devoted to some properties of the rotation-symmetric functions, namely to their weights and nonlinearity. The authors also discuss efficiency of evaluation of the truth table of the mentioned functions. In the first two sections, the authors present motivation for their research and some necessary definitions. The third section deals with the second degree rotation-symmetric function (\(f_2\)). First, some previous results on properties of the function are reviewed. Then the authors evaluate the nonlinearity of \(f_2\) in an even number of variables. Using their result they are able to display the truth table of the function with a significantly smaller number of operations than using the normal form of the function. Finally, they evaluate the weight of \(f_2\) for any dimension \(n\). In the fourth section, the third degree rotation-symmetric function (\(f_3\)) is discussed. The authors calculate the number of operations necessary to display the truth table of the function, and they evaluate the weight of the function. At the end of the section they present a conjecture about the nonlinearity of \(f_3\).