[Resource Topic] 2019/633: New non-linearity parameters of Boolean functions

Welcome to the resource topic for 2019/633

Title:
New non-linearity parameters of Boolean functions

Authors: Igor Semaev

Abstract:

The study of non-linearity (linearity) of Boolean function was initiated by Rothaus in 1976. The classical non-linearity of a Boolean function is the minimum Hamming distance of its truth table to that of affine functions. In this note we introduce new “multidimensional” non-linearity parameters (N_f,H_f) for conventional and vectorial Boolean functions f with m coordinates in n variables. The classical non-linearity may be treated as a 1-dimensional parameter in the new definition. r-dimensional parameters for r\geq 2 are relevant to possible multidimensional extensions of the Fast Correlation Attack in stream ciphers and Linear Cryptanalysis in block ciphers. Besides we introduce a notion of optimal vectorial Boolean functions relevant to the new parameters. For r=1 and even n\geq 2m optimal Boolean functions are exactly perfect nonlinear functions (generalizations of Rothaus’ bent functions) defined by Nyberg in 1991. By a computer search we find that this property holds for r=2, m=1, n=4 too. That is an open problem for larger n,m and r\geq 2. The definitions may be easily extended to q-ary functions.

ePrint: https://eprint.iacr.org/2019/633

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .