To protect data, symmetric-key ciphers rely on a property called confusion—making the relationship between the plaintext, the ciphertext, and the secret key as complex and obscured as possible. At the heart of this mechanism are Boolean functions (which map $n$ bits of input to a 1-bit output) and S-boxes (vectorial Boolean functions mapping $n$ bits to $m$ bits).
If an attacker can approximate these functions using simple linear equations, they can mount a linear cryptanalysis attack, effectively peeling back the layers of the cipher. Therefore, the primary defense is nonlinearity: a mathematical measure of how far a Boolean function is from the nearest linear (or affine) function.
To build intuition, imagine the space of all possible Boolean functions. Affine functions form a flat, predictable hyperplane. A highly nonlinear function bends and twists as far away from this hyperplane as possible, ensuring that no linear approximation can accurately guess its output.
The Perfect, Unusable Ideal: Bent Functions
In an even-dimensional space (where the number of input variables $n$ is even), there exists a class of functions that achieve the absolute maximum possible distance from all affine functions. These are known as bent functions.
Because of their perfect resistance to linear approximations, constructing bent functions is a major focus of cryptographic design. For instance, Gadouleau et al. demonstrated how to generate bent functions using Linear Bipermutive Cellular Automata, while another work by Gadouleau et al. constructed them using the kernels of linear recurring sequences.
However, bent functions have a fatal flaw for many practical applications: they are inherently unbalanced. A balanced function outputs an equal number of 0s and 1s across its entire truth table, which is vital to prevent statistical biases in stream ciphers. Bent functions cannot be balanced.
This creates a fundamental cryptographic tug-of-war. If you want perfect nonlinearity, you must sacrifice balance. If you force the function to be balanced (or resilient against correlation attacks), its nonlinearity drops. In Minimum Distance between Bent and 1-resilient Boolean Functions, Subhamoy Maitra proved the exact theoretical lower bound of bit-flips required to transform an unbalanced bent function into a 1-resilient function, mapping out the mathematical boundary of this trade-off.
The Odd-Variable Bottleneck and the Concatenation Bound
The problem becomes even more complex when the number of input variables $n$ is odd. In odd dimensions, true bent functions cannot exist. For decades, the standard recipe for building a highly nonlinear function with an odd number of variables was simple: take two lower-dimensional, even-variable bent functions and glue them together. This baseline is known as the bent concatenation bound.
For a long time, this bound acted as an empirical ceiling. It was widely conjectured that you could not surpass it. However, breaking this plateau is essential for optimizing ciphers that operate on odd bit-widths.
The breakthrough came when researchers realized that global structural symmetries could unlock higher nonlinearity. In There exist Boolean functions on n (odd) variables having nonlinearity > 2n-1 - 2(n-1)/2 if and only if n>7, Subhamoy Maitra proved that for any odd $n > 7$, functions exceeding this quadratic bent-like bound do indeed exist. Later, Subhamoy Maitra used combinatorial group theory and heuristic search to construct explicit 21-variable functions that shattered the long-standing concatenation benchmark (Patterson-Wiedemann type functions on 21 variables with Nonlinearity greater than Bent Concatenation bound).
More recently, instead of relying purely on manual algebraic constructions, researchers have turned to digital evolution. Carlet et al. demonstrated that evolutionary algorithms, when constrained by rotation-symmetric properties, can efficiently discover highly nonlinear functions in odd dimensions that defy traditional search limits.
The Multi-Dimensional Conflict: Beyond Linear Attacks
Modern ciphers do not just face linear cryptanalysis; they must simultaneously withstand algebraic attacks, differential attacks, and boomerang attacks. This turns a two-way trade-off into a complex, multi-dimensional optimization problem.
Algebraic Attacks vs. Nonlinearity
An algebraic attack attempts to express a cipher as a system of low-degree multivariate polynomial equations. To resist this, functions need high annihilator immunity. However, as Subhamoy Maitra showed in Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity, forcing maximum annihilator immunity strictly constrains the function's Walsh spectrum, directly dictating its nonlinearity via middle-weight binomial coefficients. Furthermore, Lee et al. demonstrated that functions optimized purely for linear or differential resistance can possess hidden vulnerabilities against low-degree multivariate representations.
Differential and Boomerang Uniformity
For multi-bit S-boxes, designers must minimize boomerang uniformity to protect against boomerang attacks. Durasevic et al. explored this landscape using evolutionary algorithms, revealing that boomerang uniformity presents a far more rigid and constrained fitness landscape than traditional differential uniformity. An S-box can have excellent differential properties and high nonlinearity, yet still fail to achieve optimal boomerang resistance.
Analytical Tools: From Curves to Higher-Order Logic
How do cryptographers prove these bounds without checking every possible input combination? The field relies on bridging discrete Boolean algebra with advanced geometry and alternative logics.
Algebraic Geometry
Chee et al. established a method to prove lower bounds on S-box nonlinearity by mapping vector Boolean functions to hyperelliptic curves. By applying the Weil theorem to count the rational points on these curves, they could geometrically bound the linear correlation of the function.
Higher-Order Logic
Sometimes, bit-level analysis hides vulnerabilities. Noel analyzed S-boxes using 4-valued and 16-valued logic bases, showing that while standard Boolean nonlinearity might appear constant, the cryptographic strength fluctuates depending on the underlying irreducible polynomial chosen for finite field arithmetic. This is echoed by Kazakova et al., who showed that the algebraic nonlinearity of composite multi-valued functions is directly maximized when their underlying binary components possess an odd nonlinearity distance.
Designing cryptographic components is no longer about maximizing a single metric. It is an intricate balancing act across a highly constrained mathematical landscape. Whether through algebraic geometry, combinatorial constructions, or evolutionary search, the goal remains the same: finding the rare functions that sit at the intersection of high nonlinearity, perfect balance, and robust algebraic immunity.
Key Foundational Work
S-boxes with Controllable Nonlinearity (1999) — contributed 8 concept elements to this direction.
Nonlinear Vector Resilient Functions (2001) — contributed 2 concept elements to this direction.