On Resilient Boolean Functions with Maximal Possible Nonlinearity

Yuriy Tarannikov

Paper 2000/005

On Resilient Boolean Functions with Maximal Possible Nonlinearity

Yuriy Tarannikov

Abstract

It is proved that the maximal possible nonlinearity of $n$ -variable $m$ -resilient Boolean function is $2^{n - 1} - 2^{m + 1}$ for $\frac{2 n - 7}{3} \leq m \leq n - 2$ . This value can be achieved only for optimized functions (i.~e. functions with an algebraic degree $n - m - 1$ ). For $\frac{2 n - 7}{3} \leq m \leq n - \log_{2} \frac{n - 2}{3} - 2$ it is suggested a method to construct an -variable -resilient function with maximal possible nonlinearity such that each variable presents in ANF of this function in some term of maximal possible length . For , , it is given a scheme of hardware implementation for such function that demands approximately gates EXOR and gates AND.

Metadata

Available format(s): PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: boolean functions stream ciphers secret-key cryptography implementation
Contact author(s): yutaran @ nw math msu su
taran @ vertex inria msu ru
History: 2000-03-12: received
Short URL: https://ia.cr/2000/005
License: CC BY

BibTeX

@misc{cryptoeprint:2000/005,
      author = {Yuriy Tarannikov},
      title = {On Resilient Boolean Functions with Maximal Possible Nonlinearity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2000/005},
      year = {2000},
      url = {https://eprint.iacr.org/2000/005}
}