Geodesic
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/}
}
TY  - JOUR
AU  - A. V. Khalyavin
TI  - Upper bounds on nonlinearity of correlation immune Boolean functions
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 34
EP  - 69
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_1_a3/
LA  - ru
ID  - PDM_2011_1_a3
ER  - 
%0 Journal Article
%A A. V. Khalyavin
%T Upper bounds on nonlinearity of correlation immune Boolean functions
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 34-69
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2011_1_a3/
%G ru
%F 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/

[1] Sarkar P., Maitra S., “Nonlinearity bounds and constructions of resilient boolean functions”, LNCS, 1880, 2000, 515–532 | MR | Zbl

[2] Tarannikov Yu., “On resilient Boolean functions with maximal possible nonlinearity”, LNCS, 1977, 2000, 19–30 | MR | Zbl

[3] Zheng Y., Zhang X. M., “Improved upper bound on the nonlinearity of high order correlation immune functions”, LNCS, 2012, 2001, 264–274 | MR

[4] Tarannikov Yu. V., “O korrelyatsionno-immunnykh i ustoichivykh bulevykh funktsiyakh”, Matematicheskie voprosy kibernetiki, 11, Fizmatlit, M., 2002, 91–148 | MR

[5] Khalyavin A. V., “Postroenie 4 korrelyatsionno-immunnykh bulevykh funktsii ot 9 peremennykh s nelineinostyu 240”, Materialy X Mezhdunar. seminara “Diskretnaya matematika i eë prilozheniya” (Moskva, MGU, 1–6 fevralya 2010 g.), Izd-vo mekhaniko-matematicheskogo fakulteta MGU, M., 2010, 534

[6] Botev A. A., “O sootnosheniyakh mezhdu korrelyatsionnoi immunnostyu, nelineinostyu i vesom dlya neuravnoveshennykh bulevykh funktsii”, Matematicheskie voprosy kibernetiki, 11, Fizmatlit, M., 2002, 149–162 | MR

[7] Guo-Zhen X., Massey J. A., “Spectral characterization of correlation-immune combining functions”, IEEE Trans. Information Theory, 34:3 (1988), 569–571 | DOI | MR | Zbl