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

摘要

Nonlinearity and resiliency are well known as some of themost important cryptographic parameters of Boolean functions, it isactual the problem of the constructing of functions that have high nonlinearityand resiliency simultaneously. In 2000 three groups of authorsobtained independently the upper bound 2n??1??2m+1 for the nonlinearityof an m-resilient function of n variables. It was shown that if this bound isachieved then (n??3)=2 m n??2. Simultaneously in 2000 Tarannikovconstructed functions that achieve this bound for (2n ?? 7)=3 m n ?? 2. In 2001 Tarannikov constructed such functions for 0:6n ?? 1 mintroducing for this aim so called proper matrices; later in 2001 Fedorovaand Tarannikov constructed by means of proper matrices the functionsthat achieve the bound 2n??1 ?? 2m+1 for m cn(1 + o(1)) where c =1= log2(p5 + 1) = 0:5902::: but proved simultaneously that by meansof proper matrices it is impossible to improve this result. During theperiod since 2001 it was not any further progress in the problem on theachievability of the bound 2n??1 ?? 2m+1 in spite of this problem waswell known and actual except the constructing in 2006–2007 by threegroups of authors by means of a computer search concrete functions forn = 9, m = 3. In this paper we find the new approach that uses thegeneralization of the concept of proper matrices. We formulate combinatorialproblems solutions of which allow to construct generalized propermatrices with parameters impossible for old proper matrices. As a resultwe obtain the constructions of m-resilient functions of n variables with maximal nonlinearity for m 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.