zbMATH — the first resource for mathematics

Covering sequences of Boolean functions and their cryptographic significance. (English) Zbl 1035.94009
Balancedness, correlation-immunity with high order (resiliency), high nonlinearity, and high algebraic degree are desirable features of Boolean functions for applications in cryptography. Some of these features cannot be obtained simultaneously, and a trade-off is necessary. The authors introduce the notion of covering sequence of a Boolean function, characterise balancedness and correlation immunity by means of their covering sequences, and derive upper bounds on the algebraic degree and nonlinearity of subclasses of resilient functions by considering particular covering sequences. They give constructions of resilient functions of these subclasses and show that they achieve the best known trade-off between order of resiliency, nonlinearity, and algebraic degree.

94A60 Cryptography
06E30 Boolean functions
11T23 Exponential sums
Full Text: DOI