This page is under construction!

Things to do

• List correlation immunity/resilience properites of functions.
• List propagation criterion properties for higher order than 0.
• Calculate algebraic immunity.
• Add a table of the best known functions with more than 6 variables.

-->

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, 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
  • 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₃".

^ TOP

Files

^ TOP

References

[1] J. Fuller: The Boolean Planet, (web page). [Does not seem to available any more (Feb. 2010)]

[2] A. Braeken, Y. Borissov, S. Nikova, and B. Preneel, Classification of Boolean Functions of 6 Variables or Less with Respect to Cryptographic Properties, In Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lecture Notes in Computer Science 3580, L. Caires, G. F. Italiano, and L. Monteiro (eds.), Springer-Verlag, pp. 324-334, 2005.