Paper 2000/054

Correlation Immune Boolean Functions with Very High Nonlinearity

Subhamoy Maitra

Abstract

Here we provide a construction method for unbalanced, first order correlation immune Boolean functions on even number of variables $n \geq 6$. These functions achieve the currently best known nonlinearity $2^{n-1} - 2^{\frac{n}{2}} + 2^{\frac{n}{2} - 2}$ . Then we provide a simple modification of these functions to get unbalanced correlation immune Boolean functions on even number of variables $n$, with nonlinearity $2^{n-1} - 2^{\frac{n}{2}} + 2^{\frac{n}{2} - 2} - 2$ and maximum possible algebraic degree $n-1$. Moreover, we present a detailed study on the Walsh spectra of these functions.