International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Maria Fedorova
Yuriy Tarannikov
Download:
URL: http://eprint.iacr.org/2001/083
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2001-11495,
  title={On the Constructing of Highly Nonlinear Resilient Boolean Functions by Means of Special Matrices},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / stream cipher, Boolean function, nonlinear combining function, correlation-immunity, resiliency, nonlinearity, special matrices.},
  url={http://eprint.iacr.org/2001/083},
  note={a slightly shortened version will be published in Proceedings of Indocrypt 2001 in LNCS, Springer-Verlag. yutaran@mech.math.msu.su 11600 received 5 Oct 2001},
  author={Maria Fedorova and Yuriy Tarannikov},
  year=2001
}