@inproceedings{116105612db747729bca600bc0aa595b,
title = "New results on correlation immunity",
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.",
keywords = "Absolute indicator, Correlation immunity, Linear structures, Nonlinearity, Stream ciphers",
author = "Yuliang Zheng and Zhang, {Xian Mo}",
year = "2001",
doi = "10.1007/3-540-45247-8_5",
language = "English",
isbn = "3540417826",
volume = "2015",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer, Springer Nature",
pages = "49--63",
booktitle = "Information Security and Cryptology - ICISC 2000 - 3rd International Conference, Proceedings",
address = "United States",
note = "3rd International Conference on Information Security and Cryptology, ICISC - 2000 ; Conference date: 08-12-2000 Through 09-12-2000",
}