On the nonlinearity of monotone Boolean functions

We prove a conjecture on the nonlinearity of monotone Boolean functions in even dimension, proposed in the recent paper “Cryptographic properties of monotone Boolean functions”, by Carlet et al. (J. Math. Cryptol. 10(1), 1–14, 2016). We also prove an upper bound on such nonlinearity, which is asymptotically much stronger than the conjectured upper bound and than the upper bound proved for odd dimension in this same paper. Contrary to these two previous bounds, which were not tight enough for allowing to clarify if monotone functions can have good nonlinearity, this new bound shows that the nonlinearity of monotone functions is always very bad, which represents a fatal cryptographic weakness of monotone Boolean functions; they are too closely approximated by affine functions for being usable as nonlinear components in cryptographic applications. We deduce a necessary criterion to be satisfied by a Boolean (resp. vectorial) function for being nonlinear.