New results on correlation immunity

Yuliang Zheng, Xian Mo Zhang

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

12 Citations (Scopus)


The absolute indicator for GAC forecasts the overall avalanche characteristics of a cryptographic Boolean function. From a security point of view, it is desirable that the absolute indicator of a function takes as small a value as possible. The first contribution of this paper is to prove a tight lower bound on the absolute indicator of an mth- order correlation immune function with n variables, and to show that a function achieves the lower bound if and only if it is affine. The absolute indicator for GAC achieves the upper bound when the underlying function has a non-zero linear structure. Our second contribution is about a relationship between correlation immunity and non-zero linear structures. The third contribution of this paper is to address an open problem related to the upper bound on the nonlinearity of a correlation immune function. More specifically, we prove that given any odd mth-order corre- lation immune function f with n variables, the nonlinearity of f, denoted by Nf, must satisfy Nf ≤ 2n−1 − 2m+1 for (Formula Presented) n − 1 ≤ m < 0:6n − 0:4 or f has a non-zero linear structure. This extends a known result that is stated for 0:6n − 0.4 ≤ m ≤ n − 2.

Original languageEnglish
Title of host publicationInformation Security and Cryptology - ICISC 2000 - 3rd International Conference, Proceedings
PublisherSpringer, Springer Nature
Number of pages15
ISBN (Print)3540417826, 9783540452478
Publication statusPublished - 2001
Event3rd International Conference on Information Security and Cryptology, ICISC - 2000 - Seoul, Korea, Republic of
Duration: 8 Dec 20009 Dec 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)03029743
ISSN (Electronic)16113349


Other3rd International Conference on Information Security and Cryptology, ICISC - 2000
Country/TerritoryKorea, Republic of


  • Absolute indicator
  • Correlation immunity
  • Linear structures
  • Nonlinearity
  • Stream ciphers


Dive into the research topics of 'New results on correlation immunity'. Together they form a unique fingerprint.

Cite this