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

}