Paper 2015/1036

Patterson-Wiedemann type functions on 21 variables with Nonlinearity greater than Bent Concatenation bound

Selcuk Kavut and Subhamoy Maitra

Abstract

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. Some of these Boolean functions posses nonlinearity greater than the bent concatenation bound. The next possible option for exploring 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.

Note: Revised version

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Covering RadiusFirst Order Reed-Muller CodeNonlinearityPatterson-Wiedemann Type Functions
Contact author(s)
selcukkavut @ gmail com
History
2015-10-28: last of 2 revisions
2015-10-28: received
See all versions
Short URL
https://ia.cr/2015/1036
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1036,
      author = {Selcuk Kavut and Subhamoy Maitra},
      title = {Patterson-Wiedemann type functions on 21 variables with Nonlinearity greater than Bent Concatenation bound},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1036},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1036}},
      url = {https://eprint.iacr.org/2015/1036}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.