On relationships among avalanche, nonlinearity, and correlation immunity

Yuliang Zheng; Xian Mo Zhang

On relationships among avalanche, nonlinearity, and correlation immunity

Yuliang Zheng, Xian Mo Zhang

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

24 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 ≥ 2ⁿ⁻¹ − 2ⁿ⁻¹(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 language	English
Title of host publication	Advances in Cryptology - ASIACRYPT 2000 - 6th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Publisher	Springer, Springer Nature
Pages	470-482
Number of pages	13
Volume	1976
ISBN (Electronic)	3540414045, 9783540414049
Publication status	Published - 2000
Event	6th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2000 - Kyoto, Japan Duration: 3 Dec 2000 → 7 Dec 2000

Publication series

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

Other

Other	6th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2000
Country/Territory	Japan
City	Kyoto
Period	3/12/00 → 7/12/00

Cite this

Zheng, Y., & Zhang, X. M. (2000). On relationships among avalanche, nonlinearity, and correlation immunity. In Advances in Cryptology - ASIACRYPT 2000 - 6th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (Vol. 1976, pp. 470-482). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1976). Springer, Springer Nature.

Zheng, Yuliang ; Zhang, Xian Mo. / On relationships among avalanche, nonlinearity, and correlation immunity. Advances in Cryptology - ASIACRYPT 2000 - 6th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Vol. 1976 Springer, Springer Nature, 2000. pp. 470-482 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c5a0997e461d48d9ac6813c9dc5cb127,

title = "On relationships among avalanche, nonlinearity, and correlation immunity",

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.",

author = "Yuliang Zheng and Zhang, {Xian Mo}",

year = "2000",

language = "English",

volume = "1976",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "470--482",

booktitle = "Advances in Cryptology - ASIACRYPT 2000 - 6th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "United States",

note = "6th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2000 ; Conference date: 03-12-2000 Through 07-12-2000",

}

Zheng, Y & Zhang, XM 2000, On relationships among avalanche, nonlinearity, and correlation immunity. in Advances in Cryptology - ASIACRYPT 2000 - 6th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. vol. 1976, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1976, Springer, Springer Nature, pp. 470-482, 6th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2000, Kyoto, Japan, 3/12/00.

On relationships among avalanche, nonlinearity, and correlation immunity. / Zheng, Yuliang; Zhang, Xian Mo.
Advances in Cryptology - ASIACRYPT 2000 - 6th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Vol. 1976 Springer, Springer Nature, 2000. p. 470-482 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1976).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - On relationships among avalanche, nonlinearity, and correlation immunity

AU - Zheng, Yuliang

AU - Zhang, Xian Mo

PY - 2000

Y1 - 2000

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84937399833&partnerID=8YFLogxK

M3 - Conference proceeding contribution

AN - SCOPUS:84937399833

VL - 1976

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 470

EP - 482

BT - Advances in Cryptology - ASIACRYPT 2000 - 6th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

PB - Springer, Springer Nature

T2 - 6th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2000

Y2 - 3 December 2000 through 7 December 2000

ER -

Zheng Y, Zhang XM. On relationships among avalanche, nonlinearity, and correlation immunity. In Advances in Cryptology - ASIACRYPT 2000 - 6th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Vol. 1976. Springer, Springer Nature. 2000. p. 470-482. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

On relationships among avalanche, nonlinearity, and correlation immunity

Abstract

Publication series

Other

Other files and links

Fingerprint

Cite this