On relationships among avalanche, nonlinearity, and correlation immunity

Yuliang Zheng, Xian Mo Zhang

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

17 Citations (Scopus)

Abstract

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(Formula Presented)p. We also show that the lower bound is tight, and 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 atmost n−2. These new results further highlight the significance of the fact that while avalanche property is in harmony with nonlinearity, it goes against correlation immunity.

Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2000 - 6th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
PublisherSpringer, Springer Nature
Pages470-482
Number of pages13
Volume1976
ISBN (Electronic)3540414045, 9783540414049
Publication statusPublished - 2000
Event6th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2000 - Kyoto, Japan
Duration: 3 Dec 20007 Dec 2000

Publication series

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

Other

Other6th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2000
CountryJapan
CityKyoto
Period3/12/007/12/00

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

Cite this