Lecture Notes in Computer Science, 2001, Volume 2248/2001, 460-479, DOI: 10.1007/3-540-45682-1_27

Autocorrelation Coefficients and Correlation Immunity of Boolean Functions

Yuriy Tarannikov, Peter Korolev and Anton Botev

View Related Documents

Abstract

We apply autocorrelation and Walsh coefficients for the investigation of correlation immune and resilient Boolean functions. We prove new lower bound for the absolute indicator of resilient functions that improves significantly (for m > (n - 3)/2) the bound of Zheng and Zhang [18] on this value. We prove new upper bound for the number of nonlinear variables in high resilient Boolean function. This result supersedes the previous record. We characterize all possible values of resiliency orders for quadratic functions and give a complete description of quadratic Boolean functions that achieve the upper bound on resiliency. We establish new necessary condition that connects the number of variables, the resiliency and the weight of an unbalanced nonconstant correlation immune function and prove that such functions do not exist for m > 0.75n - 1.25. For high orders of m this surprising fact supersedes the well-known Bierbrauer-Friedman bound [8], [1] and was not formulated before even as a conjecture. We improve the upper bound of Zheng and Zhang [18] for the nonlinearity ofhigh order correlation immune unbalanced Boolean functions and establish that for high orders of resiliency the maximum possible nonlinearity for unbalanced correlation immune functions is smaller than for balanced.

Keywords  Boolean functions - stream ciphers - correlation immunity - resiliency - nonlinearity - balancedness - Walsh Transform - autocorrelation coefficients - global avalanche characteristics - bounds

Fulltext Preview

Image of the first page of the fulltext document