On the Distribution of Boolean Function Nonlinearity

Abstract

Nonlinearity is the number of bits which must change in the truth table of a Boolean function to reach the closest affine function. It may be expressed through the maximum of the absolute value of a component in the function's Walsh–Hadamard transform. Concentration of nonlinearity is proved. The derived bounds on the concentration point and tails of the distribution are tighter than the earlier known ones.