Lower bounds on the higher order nonlinearities of Boolean functions and their applications to the inverse function
Claude Carlet · 2008
The nonlinearity profile of a Boolean function (i.e. the sequence of its minimum Hamming distances nlr(f) to all functions of degrees at most r, for r ges 1) is a cryptographic criterion whose role against attacks on stream and block ciphers has been illustrated by many papers. It plays also a role in coding theory, since it is related to the covering radii of Reed-Muller codes. We introduce a method for lower bounding its values and we deduce bounds on the higher order nonlinearities of the multiplicative inverse functions (used in the S-boxes of the AES).