Paper 2026/1807

A (6, 4) Vectorial Boolean Function With Nonlinearity 26 and the Maximum Nonlinearity for Six-Bit Permutations

Abstract

When the output dimension of a vectorial Boolean function exceeds half its input dimension, not all nonzero components can be bent. The best attainable componentwise nonlinearity in this range, however, is generally unknown. We ask whether the conjectured bound for even-dimensional square mappings extends to this high-output regime, and show that it does not. Specifically, we construct a six-input, four-output function with nonlinearity 26, thereby improving the previous lower bound of 24. Its seven bent components form the nonzero part of a three-dimensional component subspace, whereas the remaining eight components all have maximum absolute Walsh coefficient 12. Accordingly, the associated binary linear code has length 64, dimension 11, and minimum distance 26. We then address the distinct problem of six-bit permutations and determine its exact maximum. A computer-assisted evaluation of the complete classification of Boolean functions in six variables bounds the autocorrelation energy of every balanced component whose Walsh coefficients have magnitude at most 12. Combined with a vectorial fourth-moment identity, this bound forces every six-bit permutation to have a component with maximum absolute Walsh coefficient at least 16, and hence nonlinearity at most 24. Inversion over the field with 64 elements attains this value. Finally, the same argument gives necessary coding conditions for any non-bijective six-input, six-output function whose nonlinearity exceeds 24.