### On the nonlinearity of monotone Boolean functions

Claude Carlet

##### Abstract

We first prove the truthfulness of a conjecture on the nonlinearity of monotone Boolean functions in even dimension, proposed in the recent paper Cryptographic properties of monotone Boolean functions", by D. Joyner, P. Stanica, D. Tang and the author, to appear in the Journal of Mathematical Cryptology. We prove then 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. This bound shows a deep 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.

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
claude carlet @ gmail com
History
Short URL
https://ia.cr/2016/133

CC BY

BibTeX

@misc{cryptoeprint:2016/133,
author = {Claude Carlet},
title = {On the nonlinearity of monotone Boolean functions},
howpublished = {Cryptology ePrint Archive, Paper 2016/133},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/133}},
url = {https://eprint.iacr.org/2016/133}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.