Boolean Functions for Cryptography

Counting the Functions in Each Class

An affine equivalence class groups Boolean functions that share the same cryptographic properties. But how big is each class, that is, how many of the $2^{2^n}$ functions does it contain? The PhD research behind this site answered this exactly for every class with $n \le 6$, using what the thesis calls the self-mapping constant.

Self mappings

An affine transform maps $f$ to $g(x) = f(Dx \oplus a) \oplus b \cdot x \oplus c$, where $D$ is an invertible $n \times n$ binary matrix, $a, b \in \mathbb{Z}_2^n$ and $c \in \mathbb{Z}_2$. A transform that maps $f$ to itself is a self mapping of $f$. The identity is always one, so every function has at least one.

The thesis proves three facts about self mappings (Chapter 4):

  1. The self mappings of $f$ form a subgroup of the affine group, so their number, $\theta$, divides the order of the group.
  2. If $f$ and $g$ are equivalent, the number of distinct transforms taking $f$ to $g$ is exactly $\theta$, the number of self mappings of $f$.
  3. Equivalent functions have the same number of self mappings, so $\theta$ is a property of the whole class: the self-mapping constant.

The class-size formula

Counting the choices for $D$ (row $k$ can be any vector outside the span of the previous rows, giving $2^n - 2^k$ choices), $a$, $b$ and $c$, the total number of affine transforms is

$$\mathcal{T} = 2^{2n+1} \prod_{i=0}^{n-1} \left(2^n - 2^i\right).$$

Since every function in a class $\mathcal{C}$ is reached from $f$ by exactly $\theta$ of these transforms, the number of functions in the class is simply

$$\#\mathcal{C} = \frac{\mathcal{T}}{\theta}.$$

(This is an instance of the orbit–stabiliser theorem; the self mappings are the stabiliser of $f$ in the affine group.) The bounds follow immediately: $\theta \ge 1$, and the largest $\theta$ belongs to the smallest class, the affine functions, with $2^{n+1}$ members.

naffine transforms 𝒯
321,504
410,321,920
520,478,689,280
6165,140,150,353,920

For example, with $n = 4$ there are $15 \times 14 \times 12 \times 8 = 20{,}160$ invertible matrices, and $20{,}160 \times 16 \times 16 \times 2 = 10{,}321{,}920$ transforms.

All 48 classes for $n = 5$

Class numbers and example functions match the $n = 5$ class table. There are 33 distinct values of $\theta$, from 32 (class 35, the largest class, with 639,959,040 functions) to 319,979,520 (the affine class, with 64). The class sizes sum to exactly $2^{32} = 4{,}294{,}967{,}296$.

classexampleself maps θfunctions in class
10xaa55aa55319,979,52064
20xaa55ab559,999,3602,048
30xaa55bb55645,12031,744
40xaa5dbb5564,512317,440
50xaaddbb55258,04879,360
60xaa5dbb519,2162,222,080
70x2a5dbb511,92010,665,984
80xaaddbb519,2162,222,080
90x2a5dbf5111,5201,777,664
100x6a5dbb5172028,442,624
110x2addbb5176826,664,960
120xa8ddbb5118,4321,111,040
130xaeddda5172028,442,624
140x0a5dbf511,15217,776,640
150x8addda51144142,213,120
160xa8dd9b5176826,664,960
170x88ddbb5164,512317,440
180x88ddbb112,064,3849,920
190x8c5dda511,15217,776,640
200xa89d9b5112,2881,666,560
210x8eddda51192106,659,840
220xaefdda5172284,426,240
230x025dbf511,02419,998,720
240x88ddda5196213,319,680
250x88dd9b515,3763,809,280
260xceddda5148426,639,360
270x0eddda51144142,213,120
280x425dbf5164319,979,520
290x8cddda5148426,639,360
300x88dddb511,00820,316,160
310x289d9b5176826,664,960
320x86fdda5176826,664,960
330x88dddb714,0325,079,040
340xcefdda51120170,655,744
350x0efdda5132639,959,040
360x288d9b5176826,664,960
370x8cfdda5148426,639,360
380x8cdddb5157635,553,280
390x8ccdda5125679,994,880
400x289d9b4123,040888,832
410x488ddb51192106,659,840
420xccfdda5160341,311,488
430x688d9b51192106,659,840
440x288d9b4111,5201,777,664
450x288d1b41368,64055,552
460xdcfdda511,92010,665,984
470x68ad9b516,1443,333,120
480x688ddb511,53613,332,480

$n = 6$: the self-mapping distribution

For the 150,357 classes of $n = 6$ there are 122 distinct values of $\theta$. Most classes have no symmetry at all: 91,184 classes have $\theta = 1$ (only the identity), so each contains the full $\mathcal{T} = 165{,}140{,}150{,}353{,}920$ functions. A further 32,454 have $\theta = 2$ and 12,522 have $\theta = 4$. At the other extreme, the affine class has $\theta = 1{,}290{,}157{,}424{,}640$.

Number of $n = 6$ classes for each value of θ: all 122 values
self maps θclasses
191,184
232,454
3206
412,522
6530
74
85,590
1012
12582
148
162,665
186
2030
24506
321,275
3629
404
424
48351
608
64591
7254
96191
12018
128346
14450
1684
192183
24014
256140
28836
3204
3362
3605
384130
4326
4801
51279
5769
6401
6721
7209
76843
1,0085
1,02439
1,15254
1,2964
1,3442
1,4406
1,53672
1,9203
2,04829
2,1602
2,30413
2,8801
3,07220
3,4565
3,8408
4,0323
4,0969
4,3203
4,60824
5,0402
5,3761
5,7601
6,14422
7,6801
8,0642
8,1923
9,2162
10,7524
12,28819
13,8241
16,3842
17,2801
18,4324
23,0406
24,5763
32,2565
36,8648
40,3202
43,0081
46,0805
49,1527
56,4482
61,4401
64,5121
65,5361
73,72811
86,0162
98,3041
110,5922
120,9601
122,8803
184,3202
258,0482
294,9122
344,0641
393,2161
483,8401
589,8242
688,1281
737,2803
884,7361
1,105,9204
1,290,2401
1,451,5201
2,064,3843
2,359,2961
3,538,9441
4,128,7682
4,423,6801
14,450,6881
30,965,7602
70,778,8801
92,897,2801
115,605,5041
123,863,0401
639,959,0401
1,981,808,6401
20,158,709,7601
1,290,157,424,6401

How many functions have each nonlinearity? ($n = 6$)

Summing the class sizes over the classes at each nonlinearity gives the exact number of 6-variable functions with that nonlinearity. For nonlinearity below 16 these follow from a known closed formula, $\binom{64}{N} \cdot 2^{7}$; for 16 and above, the thesis obtained them by summing class sizes. The total is exactly $2^{64}$, and the 5,425,430,528 functions of nonlinearity 28 are precisely the bent functions, summed over the four bent classes.

nonlinearitynumber of functions
0128
18,192

Source. J. Fuller, Analysis of Affine Equivalent Boolean Functions for Cryptography, PhD thesis, QUT, 2003: Chapter 4 (self mappings, class sizes, nonlinearity counts) and Appendix 4 (tables), available from QUT ePrints; see also Millan, Fuller and Dawson, CEC 2003. All tables on this page were re-checked in 2026 against the original PhD output files. Maiorana's 1991 classification of the cosets of $\mathrm{RM}(1,6)$ records stabiliser orders in coding-theory terms.