**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)

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

[ Cryptology ePrint archive ]