New results on correlation immunity

Yuliang Zheng, Xian Mo Zhang

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

12 Citations (Scopus)

Abstract

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
Pages49-63
Number of pages15
Volume2015
ISBN (Print)3540417826, 9783540452478
DOIs
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)
Volume2015
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other3rd International Conference on Information Security and Cryptology, ICISC - 2000
CountryKorea, Republic of
CitySeoul
Period8/12/009/12/00

Keywords

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

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

  • Cite this

    Zheng, Y., & Zhang, X. M. (2001). New results on correlation immunity. In Information Security and Cryptology - ICISC 2000 - 3rd International Conference, Proceedings (Vol. 2015, pp. 49-63). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2015). Springer, Springer Nature. https://doi.org/10.1007/3-540-45247-8_5