Boolean functions are very important cryptographic
primitives in stream or block ciphers. In order to be
useful for cryptographic applications, these functions should
satisfy some properties like high algebraic degree, high non
linearity or being correlation immune. Since for most of the
cryptographic criteria presented in the literature there is no
complete characterization of the set of functions that optimally
satisfy any of them, the possibility of finding an enumerative
encoding of any such class of functions is extremely hard.
In a recent paper Le Bars and Viola have presented an
innovative recursive decomposition of the first order correlation
immune Boolean functions. It is not a trivial task, however, to
derive from this characterization an enumerative encoding.
This talk presents an enumerative encoding for first order
correlation immune functions. It provides the first enumerative
encoding of a class of Boolean functions with cryptographic
applications. The encoding naturally leads to efficient random
generation algorithms. For example, we may construct, with
uniform probability, any 1-resilient function (balanced first order
correlation immune function) with 8 variables in less than 30
seconds, from a universe of around 10^68 functions! We also present
some of the ideas behind the efficiency of the algorithms being
used.

This is a joint work with Nicolas Carrasco (U. de la Republica, Uruguay) and Jean - Marie Le Bars (U. de Caen).