You are looking at a specific version 20000312:204031 of this paper. See the latest version.

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

Metadata
Available format(s)
PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
boolean functionsstream cipherssecret-key cryptographyimplementation
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.