Connections among nonlinearity, avalanche and correlation immunity

Yuliang Zheng, Xian Mo Zhang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


Nonlinear Boolean functions play an important role in the design of block ciphers, stream ciphers and one-way hash functions. Over the years researchers have identified a number of indicators that forecast nonlinear properties of these functions. Studying the relationships among these indicators has been an area that has received extensive research. The focus of this paper is on the interplay of three notable nonlinear indicators, namely nonlinearity, avalanche and correlation immunity. We establish, for the first time, an explicit and simple lower bound on the nonlinearity Nf of a Boolean function f of n variables satisfying the avalanche criterion of degree p, namely, Nf≥2n-1-2n-1-(1/2)p. We also identify all the functions whose nonlinearity attains the lower bound. As a further contribution of this paper, we prove that except for very few cases, the sum of the degree of avalanche and the order of correlation immunity of a Boolean function of n variables is at most n-2. The new results obtained in this work further highlight the significance of the fact that while avalanche property is in harmony with nonlinearity, both go against correlation immunity.

Original languageEnglish
Pages (from-to)697-710
Number of pages14
JournalTheoretical Computer Science
Issue number3
Publication statusPublished - 31 Jan 2003


  • Avalanche criterion
  • Boolean functions
  • Correlation immunity
  • Nonlinearity


Dive into the research topics of 'Connections among nonlinearity, avalanche and correlation immunity'. Together they form a unique fingerprint.

Cite this