Cryptology ePrint Archive: Report 2004/248
Classification of Boolean Functions of 6 Variables or Less with Respect to Cryptographic Properties
An Braeken and Yuri Borissov and Svetla Nikova and Bart Preneel
Abstract: This paper presents an efficient approach for classification of
the affine equivalence classes of cosets of the first order
Reed-Muller code with respect to cryptographic properties such as
correlation-immunity, resiliency and propagation characteristics.
First, we apply the method to completely classify all the $48$
classes into which the general affine group $AGL(2,5)$ partitions
the cosets of $RM(1,5)$. Second, we describe how to find the affine
equivalence classes together with their sizes of Boolean functions in 6 variables.
We perform the same classification for these classes. Moreover, we
also determine the classification of $RM(3,7)/RM(1,7)$.
We also study the algebraic immunity of the corresponding affine equivalence classes.
Moreover, several relations are derived between the algebraic immunity
and other cryptographic properties.
Finally, we introduce two new indicators which can be used to distinguish
affine inequivalent Boolean functions when the known criteria are
not sufficient. From these indicators a method can be derived for
finding the affine relation between two functions (if such
exists). The efficiency of the method depends on the structure of
the Walsh or autocorrelation spectrum.
Category / Keywords: Boolean functions, resiliency, propagation characteristics, algebraic immunity
Date: received 24 Sep 2004, last revised 24 Feb 2005
Contact author: svetla nikova at esat kuleuven ac be
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Note: In this revised version of the paper we show how to derive the equivalence classes together with the orders of their sizes of Boolean functions in 6 variables. Using this information we classify the classes of $RM(3,6)/RM(1,6)$ according to the most important cryptographic properties. We also describe our approach to classify RM(3,7)/RM(1,7)$.
Version: 20050224:102242 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]