A Super-Set of Patterson-Wiedemann Functions - Upper Bounds and Possible Nonlinearities

Abstract

Constructing Boolean functions on odd number of variables with nonlinearity exceeding the bent concatenation bound is one of the most difficult combinatorial problems in the domain of Boolean functions and it has deep implications to coding theory and cryptology. After demonstration of such functions by Patterson and Wiedemann in 1983, for more than three decades the efforts have been channelized in obtaining the instances only. For the first time, in this paper, we try to explore non-trivial upper bounds on nonlinearity of such functions which are invariant under several group actions. In fact, we consider much larger sets of functions than what have been considered so far and obtain tight upper bounds on the nonlinearity in several cases. To support our claims, we present computational results for functions on n variables where n is an odd composite integer, 9 <= n <= 39. In particular, our results for n = 15 and 21 are of immediate interest given recent research results in this domain. Not only the upper bounds, we also identify what are the nonlinearities that can actually be achieved above the bent concatenation bound for such class of functions.