Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10]


Journal of Information Science and Engineering, Vol. 20 No. 2, pp. 305-323 (March 2004)

On Nonlinearity and Autocorrelation Properties
of Correlation Immune Boolean Functions

Subhamoy Maitra
Applied Statistics Unit
Indian Statistical Institute
Calcutta 700 108, India

In this paper we discuss the nonlinearity and autocorrelation properties of correlation immune Boolean functions. First we provide a construction method for unbalanced, first order correlation immune Boolean functions on even an number of variables n ≥ 6. These functions achieve the currently best known nonlinearity of JISEThen we provide a simple modification of these functions to get unbalanced correlation immune Boolean functions on an even number of variables n, with a nonlinearity of 2n-1JISEand a maximum possible algebraic degree of n - 1. Moreover, we present a detailed study on the Walsh spectra of these functions. Next we study the autocorrelation values of correlation immune and resilient Boolean functions. We provide new lower bounds and related results on the absolute indicator and sum of square indicator of autocorrelation values for low orders of correlation immunity. Recently it has been show that the nonlinearity and algebraic degree of correlation immune and resilient functions can be optimized simultaneously. Our analysis shows that under such a scenario, the sum of square indicator also attains its minimum value. We also point out the weakness of two recursive construction techniques for resilient functions in terms of autocorrelation values.

Keywords: algebraic degree, autocorrelation, Boolean function, correlation immunity, cryptography, global avalanche characteristics, nonlinearity, resiliency, Walsh spectra

Full Text () Retrieve PDF document (200403_06.pdf)

Received May 13, 2002; accepted April 24, 2003.
Communicated by Shiuh-Pyng Shieh.
* This paper is a combined and revised version of the papers "Correlation Immune Boolean Functions with Very High Nonlinearity," IACR ePrint Server,, N: 2000/054, Date: October 27, 2000 and "Autocorrelation Properties of Correlation Immune Boolean Functions," INDOCRYPT 2001, number 2247, LNCS, pp. 242-253, Springer Verlag, December 2001.