Boolean Functions for Cryptography

The Theorem of Connectivity

Affine equivalence groups functions that share the same cryptographic properties, but it says nothing about how those classes sit relative to one another. The theorem of connectivity supplies exactly that missing structure: it describes how a function relates to its immediate neighbours — the functions one bit-flip away in the truth table — and shows that this local structure is itself an invariant of the equivalence class. The result lets us view the whole Boolean space not as a flat collection of $2^{2^{n}}$ functions but as a set of connected equivalence classes — the cosets of $\mathrm{RM}(1,n)$ under the affine group.

The 1-local neighbourhood

The starting point is the immediate neighbourhood of a function: everything at Hamming distance one from it.

Definition. The 1-local neighbourhood of a Boolean function $f \in \mathcal{B}_n$ consists of all $2^n$ functions $f_{(i)}$, $i \in \mathbf{Z}_2^{\,n}$, with $\operatorname{dist}(f, f_{(i)}) = 1$. We say $f_{(i)}$ is connected to $f$: $$f_{(i)}(x) = \begin{cases} f(x) & x \neq i \\ f(x) \oplus 1 & x = i. \end{cases}$$

The theorem

The key result is that an affine transform maps neighbours to neighbours: if $f$ and $g$ are affine equivalent under some transform, then every neighbour of $f$ corresponds — under that same transform — to a neighbour of $g$.

Theorem (Connectivity). Let $f_{(i)}$ be defined as above. Then for $g(x) = f(\mathcal{D}x \oplus a) \oplus b \cdot x \oplus c$ there exists a connecting function $g_{(j)}$ such that $$g_{(j)}(x) = f_{(i)}(\mathcal{D}x \oplus a) \oplus b \cdot x \oplus c, \qquad j = \mathcal{D}^{-1}(i \oplus a), \qquad i = \mathcal{D}j \oplus a.$$

Because $\mathcal{D}$ is non-singular this correspondence is a bijection, which gives the property that makes connectivity useful:

Corollary. The 1-local neighbourhood of $g$ is a permutation of the 1-local neighbourhood of $f$. Repeating the argument extends this to any distance $m$: the $m$-local neighbourhood of $g$ is a permutation of that of $f$.

Connectivity between classes

Since neighbours are preserved, we can summarise a class by which classes it connects to, and how often. Every function in a class has the same connection profile. For $n = 3$, for instance, every single-bit change to a class-1 function yields a class-2 function; a class-2 function has one change leading back to class 1 and seven leading to class 3.

Equivalence class connectivity, $n = 3$

classconnecting class (frequency) distribution
1C2(8)
2C1(1), C3(7)
3C2(8)

Equivalence class connectivity, $n = 4$

classconnecting class (frequency) distribution
1C2(16)
2C1(1), C3(15)
3C2(2), C4(14)
4C3(3), C5(1), C6(12)
5C4(16)
6C4(8), C7(8)
7C6(15), C8(1)
8C7(16)

The $n = 5$ connectivity profile follows the same form across its 48 classes (see the equivalence class tables for the classes themselves).

Class connection diagrams

Drawing one node per class and one branch per connection turns the space into a tree. Arranged by nonlinearity, the affine class sits at the root and the maximally nonlinear classes — including the bent classes for even $n$ — form the topmost leaves. The branches are sparse near the top (high-nonlinearity classes have few connections) and grow thicker toward the root, revealing the inherent shape of the Boolean space.

Class connection diagram, n = 3Tree of the three n=3 equivalence classes connected by single-bit changes, arranged by nonlinearity from the affine class at the root to class 3 at the top.NL 2NL 1NL 0123
Class connection diagram, n = 3
Class connection diagram, n = 4Tree of the eight n=4 equivalence classes connected by single-bit changes, arranged by nonlinearity from the affine class at the root to the bent class 8 at the top.NL 6NL 5NL 4NL 3NL 2NL 1NL 012345678
Class connection diagram, n = 4
affine class (root) bent class

For $\mathcal{B}_3$ the tree is a simple chain; for $\mathcal{B}_4$ it begins to branch, with class 5 forming a leaf at nonlinearity 4 and the bent class 8 at the very top. The diagram for the 48 classes of $\mathcal{B}_5$ is far richer but follows the same principle; only a partial, high-nonlinearity component is feasible for $\mathcal{B}_6$.

Why it matters

The connection profile is an affine invariant, so it is a powerful tool for telling classes apart and for navigating the space:

The theorem of connectivity was the foundation of the PhD research from which this site grew — the result that turns the unmanageable Boolean space into a navigable structure.