JISE


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


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


On Nonlinearity and Autocorrelation Properties of Correlation Immune Boolean Functions


Subhamoy Maitra
Applied Statistics Unit 
Indian Statistical Institute 
Calcutta 700 108, India 
E-mail: subho@isical.ac.in


    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

  Retrieve PDF document (JISE_200402_06.pdf)