Cryptology ePrint Archive: Report 2001/083

On the Constructing of Highly Nonlinear Resilient Boolean Functions by Means of Special Matrices

Maria Fedorova and Yuriy Tarannikov

Abstract: In this paper we consider matrices of special form introduced in [11] and used for the constructing of resilient functions with cryptographically optimal parameters. For such matrices we establish lower bound ${1\over\log_2(\sqrt{5}+1)}=0.5902...$ for the important ratio ${t\over t+k}$ of its parameters and point out that there exists a sequence of matrices for which the limit of ratio of its parameters is equal to lower bound. By means of these matrices we construct $m$-resilient $n$-variable functions with maximum possible nonlinearity $2^{n-1}-2^{m+1}$ for $m=0.5902...n+O(\log_2 n)$. This result supersedes the previous record.

Category / Keywords: secret-key cryptography / stream cipher, Boolean function, nonlinear combining function, correlation-immunity, resiliency, nonlinearity, special matrices.

Publication Info: a slightly shortened version will be published in Proceedings of Indocrypt 2001 in LNCS, Springer-Verlag.

Date: received 5 Oct 2001

Contact author: yutaran at mech math msu su

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20011005:202242 (All versions of this report)

Short URL: ia.cr/2001/083

Discussion forum: Show discussion | Start new discussion