Paper 2004/248

Classification of Boolean Functions of 6 Variables or Less with Respect to Cryptographic Properties

An Braeken, Yuri Borissov, Svetla Nikova, and Bart Preneel


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.

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)$.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Boolean functionsresiliencypropagation characteristicsalgebraic immunity
Contact author(s)
svetla nikova @ esat kuleuven ac be
2005-02-24: last of 8 revisions
2004-09-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {An Braeken and Yuri Borissov and Svetla Nikova and Bart Preneel},
      title = {Classification of Boolean Functions of 6 Variables or Less with Respect to Cryptographic Properties},
      howpublished = {Cryptology ePrint Archive, Paper 2004/248},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.