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

Y. V. Tarannikov

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 229-245

Résumé

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 non-linearity and resiliency simultaneously. In 2000 three groups of authors 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 combinatorial 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$.

Détail

Keywords: Boolean functions, symmetric-key cryptography, nonlinearity, resiliency, maximal possible nonlinearity, bounds, plateaued functions, implementation complexity.
Mots-clés : constructions