Boolean Functions: The Basics
This page builds up the main cryptographic measures of a Boolean function step by step, using one small example throughout: the majority function on three inputs, which outputs 1 when at least two of its inputs are 1. Every number here is computed directly from the definitions.
1. Truth table
A Boolean function of $n$ inputs is a map $f: \{0,1\}^n \to \{0,1\}$. The most direct
description is its truth table: the output for each of the $2^n$ inputs. We
number the inputs $x = (x_1, x_2, x_3)$ by $i = x_1 + 2x_2 + 4x_3$. Reading the outputs as bits
$f(0), f(1), \ldots$ (least significant first) gives the hexadecimal form used on this site:
majority is 0xe8.
| i | x = (x₁,x₂,x₃) | f(x) | ANF coefficient |
|---|---|---|---|
| 0 | (0,0,0) | 0 | 0 |
| 1 | (1,0,0) | 0 | 0 |
| 2 | (0,1,0) | 0 | 0 |
| 3 | (1,1,0) | 1 | 1 |
| 4 | (0,0,1) | 0 | 0 |
| 5 | (1,0,1) | 1 | 1 |
| 6 | (0,1,1) | 1 | 1 |
| 7 | (1,1,1) | 1 | 0 |
The Hamming weight is the number of 1s: here 4 of 8, so the function is balanced (equally many 0s and 1s), which is essential for most cryptographic uses: an unbalanced output leaks a statistical bias.
2. Algebraic normal form and degree
Every Boolean function can be written uniquely as an XOR of AND-terms, its algebraic normal form (ANF). The coefficients (last column above) come from the truth table by the binary Möbius transform. For majority:
$$f(x) = x_1x_2 \oplus x_1x_3 \oplus x_2x_3.$$
The algebraic degree (or order) is the size of the largest term: here 2. Degree 1 functions are affine (linear plus a constant) and offer no security; higher degree resists algebraic attacks.
3. Walsh–Hadamard transform
The Walsh–Hadamard transform measures how strongly $f$ correlates with each linear function $\omega \cdot x$:
$$\hat F(\omega) = \sum_{x} (-1)^{f(x) \oplus \omega \cdot x}.$$
A value of 0 means no correlation; $\pm 2^n$ means $f$ equals that linear function (or its complement).
| ω | linear function ω·x | F̂(ω) |
|---|---|---|
| (0,0,0) | $0$ | 0 |
| (1,0,0) | $x_1$ | 4 |
| (0,1,0) | $x_2$ | 4 |
| (1,1,0) | $x_1 \oplus x_2$ | 0 |
| (0,0,1) | $x_3$ | 4 |
| (1,0,1) | $x_1 \oplus x_3$ | 0 |
| (0,1,1) | $x_2 \oplus x_3$ | 0 |
| (1,1,1) | $x_1 \oplus x_2 \oplus x_3$ | -4 |
4. Nonlinearity
The nonlinearity is the Hamming distance from $f$ to the nearest affine function, and it comes straight from the largest Walsh value:
$$\mathrm{NL}(f) = 2^{n-1} - \tfrac12 \max_\omega |\hat F(\omega)| = 4 - \tfrac12 \cdot 4 = 2.$$
High nonlinearity defends against linear cryptanalysis, which exploits correlation with linear functions. For $n = 3$, 2 is the largest nonlinearity possible, so majority is as good as a 3-input function gets.
For even $n$ the maximum, $2^{n-1} - 2^{n/2-1}$, is reached by bent functions, whose
Walsh values all have the same magnitude $2^{n/2}$. The classic example for $n = 4$ is
$x_1x_2 \oplus x_3x_4$ (0x7888): every $|\hat F(\omega)| = 4$, and its
nonlinearity is 6. Bent functions are never balanced, which is why balanced functions
of high nonlinearity are a central research problem (see Records).
5. Autocorrelation
The autocorrelation measures how $f$ changes when the input is shifted by $s$:
$$\hat r(s) = \sum_x (-1)^{f(x) \oplus f(x \oplus s)}.$$
| shift s | r̂(s) |
|---|---|
| (0,0,0) | 8 |
| (1,0,0) | 0 |
| (0,1,0) | 0 |
| (1,1,0) | 0 |
| (0,0,1) | 0 |
| (1,0,1) | 0 |
| (0,1,1) | 0 |
| (1,1,1) | -8 |
$\hat r(0) = 2^n$ always. Large values for $s \ne 0$ indicate predictable behaviour under input differences, the weakness exploited by differential cryptanalysis. The largest magnitude over $s \ne 0$ is the absolute indicator (the acmax used in this site's tables); for majority it is 8, the worst possible. Flipping all three inputs always flips the output ($\hat r(1,1,1) = -8$), a so-called linear structure. So majority is optimal for nonlinearity but weak here: good functions must balance several criteria at once, which is what makes their design hard.
6. Affine equivalence
Changing variables affinely, adding an affine function, or complementing the output, $g(x) = f(Dx \oplus a) \oplus b \cdot x \oplus c$, preserves nonlinearity, degree (above 1) and the absolute Walsh and autocorrelation distributions. So functions fall into equivalence classes that share these properties. For $n = 3$ there are only three classes, and majority belongs to class 3, the class of maximum nonlinearity. Instead of studying all $2^{2^n}$ functions, one representative per class suffices: see the equivalence class tables, and how big each class is.
Note that Hamming weight is not preserved (adding $b \cdot x$ changes it), so a class can contain both balanced and unbalanced functions.
Where next
- Efficient Implementation: computing these transforms fast, with word packing.
- The Theorem of Connectivity: how the classes link together.
- Learning: books and courses for going further.