On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2

Abstract

We improve parts of the results of [T. W. Cusick, P. Stanica, Fast evaluation, weights and nonlinearity of rotation-symmetric functions, Discrete Mathematics 258 (2002) 289-301; J. Pieprzyk, C. X Qu, Fast hashing and rotation-symmetric functions, journal of Universal Computer Science 5 (1) (1999) 20-31]. It is observed that the n-variable quadratic Boolean functions, f(n,s)(chi) := E(i=1)(n) chi(i)chi(i+s-1) for 2 <= s <= inverted right perpendicularn/2inverted left perpendicular, which are homogeneous rotation symmetric, may not be affinely equivalent for fixed n and different choices of s. We show that their weights and nonlinearity are exactly characterized by the cyclic subgroup (s - 1) of Z(n). If n/gcd(n,s-1), the order of s - 1, is even, the weight and nonlinearity are the same and given by 2(n-1) - 2(n/2+gcd(n,s-1)-1). If the order is odd, it is balanced and nonlinearity is given by 2(n-1) - 2(n+gcd(n,s-1)/2) (C) 2008 Elsevier B.V. All rights reserved.