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

**Category / Keywords: **secret-key cryptography / Boolean functions, symmetric-key cryptography, nonlinearity, resiliency, maximal possible nonlinearity, bounds, plateaued functions, constructions, implementation complexity

**Original Publication**** (with minor differences): **Siberian Electronic Mathematical Reports, Volume 11 (2014), pp.229-245; semr.math.nsc.ru

**Date: **received 3 Mar 2014, last revised 24 Mar 2014

**Contact author: **taran at butovo com

**Available format(s): **PDF | BibTeX Citation

**Version: **20140324:155317 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]