@inproceedings{2dd6f46fbce5417eb0b94e01691b862c,
title = "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.",
keywords = "Covering radius, First order Reed-Muller code, Nonlinearity bound, Patterson-Wiedemann type functions",
author = "Sel{\c c}uk Kavut and Subhamoy Maitra and Ferruh {\"O}zbudak",
year = "2017",
doi = "10.1007/978-3-319-55227-9_16",
language = "English",
isbn = "978-3-319-55226-2",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer VS",
pages = "227--242",
booktitle = "Arithmetic of Finite Fields",
note = "6th International Workshop on Arithmetic of Finite Fields, WAIFI 2016 ; Conference date: 13-07-2016 Through 15-07-2016",
}