Introduction

A Boolean function of n variables is a function ƒ: Z₂ⁿ → Z₂. Such functions are used to construct and analyse cryptographic systems.

Equivalence classes of Boolean functions can be defined with respect to various symmetries:

A) Variable permutations

ƒ(x₀, x₁, …, x_n-1) = ƒ(x_p(0), x_p(1), …, x_p(n-1)).

B) Variable complementations

ƒ(x) = ƒ(x + a).

C) Affine offset

ƒ(x) = ƒ(x) + b ⋅ x + c.

D) Linear mapping

ƒ(x) = ƒ(xA), where A is an invertible binary matrix.

Different properties of Boolean functions are equivalent with respect to different symmetries:

Properties equivalent with respect to A, B, C, and D

• Algebraic degree.
• Non-linearity.
• Absolute distribution of the coefficients of Walsh spectrum and autocorrelation spectrum. (Order and signs may change.)

Properties equivalent with respect to A, B, and C.

• Maximum satisfied degree of the propagation criterion.

Properties equivalent with respect to A.

• Balancedness.
• Maximum order of correlation immunity.
• Maximum order of resilience.

All equivalence classes of Boolean functions of up to 6 variables with respect to A, B, C, and D are available from [1]. Propagation criterion and correlation immunity of Boolean functions of up to 6 variables have been analysed in [2].

^ TOP

Tables

Number of equivalence classes of Boolean functions with respect to symmetries A, B, C, and D. (These numbers are also found as sequence A001289 in the On-Line Encyclopedia of Integer Sequences.)

n	1	2	3	4	5	6
#	1	2	3	8	48	150,357

Number of equivalence classes of Boolean functions with respect to symmetries A, B, and C.

n	1	2	3	4	5
#	1	2	5	39	22,442

The number of equivalence classes of Boolean functions with 6 variables and degree less than or equal to 3 is 851,520.

^ TOP

File formats

The equivalence classes with respect to A, B, C, and D are listed in a file consisting of records of the following format:

• number of variables
• algebraic degree
• non-linearity
• absolute distribution of the coefficients of the Walsh spectrum
  • Example: "(0,24)(8,7)(24,1)" means that there are 24 coefficients with value 0, 7 coefficients with abs. value 8, and 1 coefficient with abs. value 24.
• absolute distribution of the coefficients of the autocorrelation spectrum
• a Boolean function from the class
  • The Boolean functions are given in algebraic normal form notation. Example: "03,13,23" is the function "x₀x₃+x₁x₃+x₂x₃".

The equivalence classes with respect to A, B, and C are listed in a file consisting of records of the following format:

• number of variables
• algebraic degree
• non-linearity
• maximum satisfied degree of the propagation criterion
• absolute distribution of the coefficients of the Walsh spectrum
• absolute distribution of the coefficients of the autocorrelation spectrum
• a Boolean function from the class

^ TOP

Files

^ TOP

References

[1] Joanne Fuller: The Boolean Planet, (web page).

[2] An Braeken, Yuri Borissov, Svetla Nikova, and Bart Preneel: Classification of Boolean Functions of 6 Variables or Less with Respect to Cryptographic Properties, (preprint).