International Association
for Cryptologic Research

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