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 correlation immune.
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 Haddamard conjecture!
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.