Auto-correlations and new bounds on the nonlinearity of boolean functions

Xian Mo Zhang, Yuliang Zheng

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

16 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationAdvances in Cryptology - EUROCRYPT 1996 - International Conference on the Theory and Application of Cryptographic Techniques, Proceedings
PublisherSpringer, Springer Nature
Pages294-306
Number of pages13
Volume1070
ISBN (Print)354061186X, 9783540611868
Publication statusPublished - 1996
Event15th International conference on Theory and Application of Cryptographic Techniques, EUROCRYPT 1996 - Saragossa, Spain
Duration: 12 May 199616 May 1996

Publication series

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

Other

Other15th International conference on Theory and Application of Cryptographic Techniques, EUROCRYPT 1996
CountrySpain
CitySaragossa
Period12/05/9616/05/96

Fingerprint Dive into the research topics of 'Auto-correlations and new bounds on the nonlinearity of boolean functions'. Together they form a unique fingerprint.

Cite this