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^{n1}2^{m+1}$ for ${2n7\over 3}\le m\le n2$. This value can be achieved only for optimized functions (i.~e. functions with an algebraic degree $nm1$). For ${2n7\over 3}\le m\le n\log_2{n2\over 3}2$ it is suggested a method to construct an $n$variable $m$resilient function with maximal possible nonlinearity $2^{n1}2^{m+1}$ such that each variable presents in ANF of this function in some term of maximal possible length $nm1$. For $n\equiv 2\pmod 3$, $m={2n7\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
 Secretkey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 boolean functionsstream cipherssecretkey cryptographyimplementation
 Contact author(s)

yutaran @ nw math msu su
taran @ vertex inria msu ru  History
 20000312: 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}, note = {\url{https://eprint.iacr.org/2000/005}}, url = {https://eprint.iacr.org/2000/005} }