Cryptology ePrint Archive: Report 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$.

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;

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)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]