Upper bounds on nonlinearity of correlation immune Boolean functions
Prikladnaâ diskretnaâ matematika, no. 1 (2011), pp. 34-69
Voir la notice de l'article provenant de la source Math-Net.Ru
It is known that $\mathrm{nl}(f)\le 2^{n-1}-2^m$ for the nonlinearity $\mathrm{nl}(f)$ of any Boolean function $f$ with $n$ variables and with the correlation immunity order $m$. We prove that for all $n\ge512$ and $0$, except two cases: $m=2^s$, $n=2^{s+1}+1$ and $m=2^s+1$, $n=2^{s+1}+2$ for $s\ge0$, this bound can be improved up to $\mathrm{nl}(f)\le2^{n-1}-2^{m+1}$. Besides, we have checked this result for $n512$, $0$ using computer.
Keywords:
Boolean functions, nonlinearity, correlation immunity.
@article{PDM_2011_1_a3,
author = {A. V. Khalyavin},
title = {Upper bounds on nonlinearity of correlation immune {Boolean} functions},
journal = {Prikladna\^a diskretna\^a matematika},
pages = {34--69},
publisher = {mathdoc},
number = {1},
year = {2011},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/PDM_2011_1_a3/}
}
A. V. Khalyavin. Upper bounds on nonlinearity of correlation immune Boolean functions. Prikladnaâ diskretnaâ matematika, no. 1 (2011), pp. 34-69. http://geodesic.mathdoc.fr/item/PDM_2011_1_a3/