Boolean Functions for Cryptography

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.

ix = (x₁,x₂,x₃)f(x)ANF coefficient
0(0,0,0)00
1(1,0,0)00
2(0,1,0)00
3(1,1,0)11
4(0,0,1)00
5(1,0,1)11
6(0,1,1)11
7(1,1,1)10

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 ω·xF̂(ω)
(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 sr̂(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