Paper 2006/459

Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications

Claude Carlet

Abstract

The nonlinearity profile of a Boolean function (i.e. the sequence of its minimum Hamming distances $nl_r(f)$ to all functions of degrees at most $r$, for $r\geq 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 second order nonlinearity for several classes of cryptographic Boolean functions, including the Welch and the multiplicative inverse functions (used in the S-boxes of the AES). In the case of this last infinite class of functions, we are able to bound the whole profile, and we do it in an efficient way when the number of variables is not too small. This allows showing the good behavior of this function with respect to this criterion as well.

Note: Several results have been improved and completed

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
claude carlet @ inria fr
History
2007-11-12: last of 2 revisions
2006-12-05: received
See all versions
Short URL
https://ia.cr/2006/459
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/459,
      author = {Claude Carlet},
      title = {Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/459},
      year = {2006},
      url = {https://eprint.iacr.org/2006/459}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.