**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
${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.

**Category / Keywords: **secret-key cryptography / boolean functions, stream ciphers, secret-key cryptography, implementation

**Date: **received 10 Mar 2000

**Contact author: **yutaran at nw math msu su, taran@vertex inria msu ru

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20000312:204031 (All versions of this report)

**Short URL: **ia.cr/2000/005

[ Cryptology ePrint archive ]