Paper 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.
Metadata
- Available format(s)
- PS
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. a slightly shortened version will be published in Proceedings of Indocrypt 2001 in LNCS, Springer-Verlag.
- Keywords
- stream cipherBoolean functionnonlinear combining functioncorrelation-immunityresiliencynonlinearityspecial matrices.
- Contact author(s)
- yutaran @ mech math msu su
- History
- 2001-10-05: received
- Short URL
- https://ia.cr/2001/083
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2001/083,
author = {Maria Fedorova and Yuriy Tarannikov},
title = {On the Constructing of Highly Nonlinear Resilient Boolean Functions by Means of Special Matrices},
howpublished = {Cryptology ePrint Archive, Paper 2001/083},
year = {2001},
note = {\url{https://eprint.iacr.org/2001/083}},
url = {https://eprint.iacr.org/2001/083}
}
