Covering sequences of Boolean functions and their cryptographic significance (Q1862444)

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.