Paper 2022/1777

Weightwise perfectly balanced functions and nonlinearity

Agnese Gini, University of Luxembourg, Luxembourg
Pierrick Méaux, University of Luxembourg, Luxembourg
Abstract

In this article we realize a general study on the nonlinearity of weightwise perfectly balanced (WPB) functions. First, we derive upper and lower bounds on the nonlinearity from this class of functions for all $n$. Then, we give a general construction that allows us to provably provide WPB functions with nonlinearity as low as $2^{n/2-1}$ and WPB functions with high nonlinearity, at least $2^{n-1}-2^{n/2}$. We provide concrete examples in $8$ and $16$ variables with high nonlinearity given by this construction. In $8$ variables we experimentally obtain functions reaching a nonlinearity of $116$ which corresponds to the upper bound of Dobbertin's conjecture, and it improves upon the maximal nonlinearity of WPB functions recently obtained with genetic algorithms. Finally, we study the distribution of nonlinearity over the set of WPB functions. We examine the exact distribution for $n=4$ and provide an algorithm to estimate the distributions for $n=8$ and $16$, together with the results of our experimental studies for $n=8$ and $16$.

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
Boolean functionsWeightwise perfectly balanced functionNonlinearity
Contact author(s)
agnese gini @ uni lu
pierrick meaux @ uni lu
History
2022-12-31: approved
2022-12-29: received
See all versions
Short URL
https://ia.cr/2022/1777
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1777,
      author = {Agnese Gini and Pierrick Méaux},
      title = {Weightwise perfectly balanced functions and nonlinearity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1777},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1777}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.