@inproceedings{017adaf9dcf442fa9a5c746667a5dde1,
title = "Auto-correlations and new bounds on the nonlinearity of boolean functions",
abstract = "It is a well known fact that the nonlinearity of a function f on the n-dimensional vector space V n is bounded from above by 2n−1 − 21/2n−1. In cryptographic practice, nonlinear functions are usually constructively obtained in such a way that they support certain mathematical or cryptographic requirements. Hence an important question is how to calculate the nonlinearity of a function when extra information is available. In this paper we address this question in the context of auto-correlations, and derive four (two upper and two lower) bounds on the nonlinearity of a function (see Table 1). Strengths and weaknesses of each bound are also examined. In addition, a few examples are given to demonstrate the usefulness of the bounds in practical applications. We anticipate that these four bounds will be very useful in calculating the nonlinearity of a cryptographic function when certain extra information on the auto-correlations of the function is available.",
author = "Zhang, {Xian Mo} and Yuliang Zheng",
year = "1996",
language = "English",
isbn = "354061186X",
volume = "1070",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer, Springer Nature",
pages = "294--306",
booktitle = "Advances in Cryptology - EUROCRYPT 1996 - International Conference on the Theory and Application of Cryptographic Techniques, Proceedings",
address = "United States",
note = "15th International conference on Theory and Application of Cryptographic Techniques, EUROCRYPT 1996 ; Conference date: 12-05-1996 Through 16-05-1996",
}