Enumerative Coding of 1-resiliente Boolean functions
Alfredo Viola (Montevideo - Uruguay )
Thursday 17 June 2010, 15.00, b-it 1.25 (cosec meeting room)
Contents
Cryptographic transformations (like pseudo-random generators in stream ciphers, S-boxes in block ciphers, etc.) can be designed by appropriate
composition of nonlinear Boolean functions. Several desired properties
of Boolean functions to be used in cryptographic applications have been proposed.
There is an extensive literature oriented to present constructions of classes of Boolean function with some specific cryptographic propertis. To the contrary, there are very few papers oriented to completely characterize the set of all Boolean functions in n variables that satisfy some specific criteria.
In a recent paper, Le Bars and Viola have presented a novel combinatorial approach called the "method of classes", that lead them to completely chararcterize the set of all 1-resilient functions in n variables. This approach lead to the use of generating functions that allowed a very precise asymptotic counting of the number of these functions. Moreover efficient implementeations of the algorithms presented in that paper, lead to the exact counting of the number of 1-resilient funcitons in 7 and 8 variables.
In this talk, we present one of the main contributions of this novel approach: efficient algorithms to uniformily generate 1-resilient functions up to 8 variables. These algorithms are based on the efficient use of the tables generated in the counting algorithms presented in the paper by Le Bars and Viola that lead to an enumerative coding of these functions. This work has been done together with Jean-Marie Le Bars (Universite de Caen, France) and Nicolas Carrasco (Univesidad de la Republica, Uruguay).