Séminaire APR: Advances in the combinatorial characterization of correlation-immune Boolean functions
Intervenant(s) : Alfredo Viola (Universidad de la República de Uruguay)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
In 2010 we presented a complete characterization of the first
order correlation immune Boolean functions that includes the
functions that are 1-resilient. Our approach consists in defining
an equivalence relation on the full set of Boolean functions
with a fixed number of variables. An equivalence class in this
relation, called a first-order correlation class, provides a measure
of the distance between the Boolean functions it contains and
the correlation-immune Boolean functions. The key idea consists
on manipulating only the equivalence classes instead of the
set of Boolean functions.
As far a we know this was the first complete characterization of a set of
Boolean functions for cryptographic applications. Moreover, we can
efficiently generate uniform at random any function of any class by means
of an enumerative encoding.
In 2014 Claude Carlet asked us to extend this work to higher order
correlation-immune fuctions with minimum weights. These functions are used
to mask sboxes in hardware implementations of AES to resist side-channel
emanations leaking from these cryptographic implementations.
This problem has turned to be very challenging has relations with
combinatorial designs, coding theory, combinatorics and even with the
In this talk we present the combinatorial method we use to characterize
k-correlation immune functions of minimal weight and our algorithmic
approach. This is still an ongoing research.
Joint work with Jean-Marie Le Bars, Nicolás Carrasco, Francisco Castro,
Sebastián Fonseca, María Cecilia García and Octavio Pérez Kempner.