International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: On Resilient Boolean Functions with Maximal Possible Nonlinearity

Authors:
Yuriy Tarannikov
Download:
URL: http://eprint.iacr.org/2000/005
Search ePrint
Search Google
Abstract: It is proved that the maximal possible nonlinearity of $n$-variable $m$-resilient Boolean function is $2^{n-1}-2^{m+1}$ for ${2n-7\over 3}\le m\le n-2$. This value can be achieved only for optimized functions (i.~e. functions with an algebraic degree $n-m-1$). For ${2n-7\over 3}\le m\le n-\log_2{n-2\over 3}-2$ it is suggested a method to construct an $n$-variable $m$-resilient function with maximal possible nonlinearity $2^{n-1}-2^{m+1}$ such that each variable presents in ANF of this function in some term of maximal possible length $n-m-1$. For $n\equiv 2\pmod 3$, $m={2n-7\over 3}$, it is given a scheme of hardware implementation for such function that demands approximately $2n$ gates EXOR and $(2/3)n$ gates AND.
BibTeX
@misc{eprint-2000-11349,
  title={On Resilient Boolean Functions with Maximal Possible Nonlinearity},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / boolean functions, stream ciphers, secret-key cryptography, implementation},
  url={http://eprint.iacr.org/2000/005},
  note={ yutaran@nw.math.msu.su, taran@vertex.inria.msu.ru 11026 received 10 Mar 2000},
  author={Yuriy Tarannikov},
  year=2000
}