Paper 2014/164

Generalized proper matrices and constructing of $m$-resilient Boolean functions with maximal nonlinearity for expanded range of parameters

Yuriy Tarannikov

Abstract

Nonlinearity and resiliency are well known as some of the most important cryptographic parameters of Boolean functions, it is actual the problem of the constructing of functions that have high nonlinearity and resiliency simultaneously. In 2000 three groups of au\-thors obtained independently the upper bound $2^{n-1}-2^{m+1}$ for the nonlinearity of an $m$-resilient function of $n$ variables. It was shown that if this bound is achieved then $(n-3)/2\le m\le n-2$. Simultaneously in 2000 Tarannikov constructed functions that achieve this bound for $(2n-7)/3\le m\le n-2$. In 2001 Tarannikov constructed such functions for $0.6n-1\le m$ introducing for this aim so called proper matrices; later in 2001 Fedorova and Tarannikov constructed by means of proper matrices the functions that achieve the bound $2^{n-1}-2^{m+1}$ for $m\ge cn(1+o(1))$ where $c=1/\log_2(\sqrt{5}+1)=0.5902...$ but proved simultaneously that by means of proper matrices it is impossible to improve this result. During the period since 2001 it was not any further progress in the problem on the achievability of the bound $2^{n-1}-2^{m+1}$ in spite of this problem was well known and actual except the constructing in 2006--2007 by three groups of authors by means of a computer search concrete functions for $n=9$, $m=3$. In this paper we find the new approach that uses the generalization of the concept of proper matrices. We formulate com\-bi\-na\-to\-ri\-al problems solutions of which allow to construct generalized proper matrices with parameters impossible for old proper matrices. As a result we obtain the constructions of $m$-resilient functions of $n$ variables with maximal nonlinearity for $m\ge cn(1+o(1))$ where $c=0.5789...$, and also we demonstrate how further advance in combinatorial problems follows an additional decrease of the constant $c$.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. Siberian Electronic Mathematical Reports, Volume 11 (2014), pp.229-245; semr.math.nsc.ru
Keywords
Boolean functionssymmetric-key cryptographynonlinearityresiliencymaximal possible nonlinearityboundsplateaued functionsconstructionsimplementation complexity
Contact author(s)
taran @ butovo com
History
2014-03-24: revised
2014-03-03: received
See all versions
Short URL
https://ia.cr/2014/164
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/164,
      author = {Yuriy Tarannikov},
      title = {Generalized proper matrices and constructing of $m$-resilient Boolean functions with maximal nonlinearity for expanded range of parameters},
      howpublished = {Cryptology ePrint Archive, Paper 2014/164},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/164}},
      url = {https://eprint.iacr.org/2014/164}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.