IACR News item: 27 October 2015
Selcuk Kavut, Subhamoy Maitra
ePrint Report
Nonlinearity is one of the most challenging combinatorial property in the domain of Boolean function research. Obtaining nonlinearity greater than the bent concatenation bound for odd number of variables continues to be one of the most sought after combinatorial research problems. The pioneering result in this direction has been discovered by Patterson and Wiedemann in 1983 (IEEE-IT), which considered Boolean functions on $5 \\times 3 = 15$ variables that are invariant under the actions of the cyclic group
${GF(2^5)}^\\ast \\cdot {GF(2^3)}^\\ast$ as well as the group of Frobenius authomorphisms. Such Boolean functions posses nonlinearity greater than the bent concatenation bound, namely $2^{n-1} - 2^{\\frac{n-1}{2}}$. The next possible option for obtaining such functions is on $7 \\times 3 = 21$ variables. However, obtaining such functions remained elusive for more than three decades even after substantial efforts as evident in the literature. In this paper, we exploit combinatorial arguments together with heuristic search to demonstrate such functions for
the first time.
Additional news items may be found on the IACR news page.