Counting first-order correlation-immune functions

Boolean functions are very important cryptographic primitives in stream or block ciphers. In this context, these functions need to satisfy good properties like high algebraic degree, nonlinearity and correlation immunity. We present here an original and efficient method to enumerate all the correlation-immune functions of a fixed Hamming weigth, in particular the class of $1$-resilient functions. The key idea consists in defining equivalent classes to split boolean functions along their distance from correlation-immune boolean functions. These classes, called first-order correlation classes, are built using a recursive decomposition of smaller classes. We derive from this method several algorithms to enumerate their elements and to count their cardinality.

We first show that the exact number of $1$-resilient boolean functions with $7$ variables is $23478015754788854439497622689296$ and we obtain a tight estimation of their number with $8$ variables, between $4\;10^{67}$ and $5.6\;10^{68}$. We then present a general lower bound for the number of $1$-resilient boolean functions and improve Schneider's upper bound. We also propose a general lower bound for the number of $k$-resilient functions. Most of the bounds presented in this paper, substantially improve the best known bounds in the literature. We finally establish that the probability of a Boolean function being $1$-resilient is asymptotically between $\frac{\left(n\pi\right)^{n/2}}{2^{n^2-\frac{3}{2}n-1}e^{n-1/2}}$ and $2^{-\frac{n^2}{4}+\frac{n}{4}}$. We also present some ideas about how we may be able to find the exact asymptotic value of this probability.

This is joint work with Jean-Marie Le Bars from University of Caen.