In symmetric-key cryptography, the security of stream ciphers and block ciphers rests on the mathematical properties of their nonlinear components: Boolean functions and Substitution Boxes (S-boxes). Ideally, these components would be perfectly resistant to every known attack while remaining trivial to implement in hardware. In practice, designers face a fundamental "tug-of-war" where optimizing for one security metric almost inevitably degrades another.
The Nonlinearity and Resiliency Conflict
The most basic requirement for a cryptographic Boolean function is nonlinearity—the measure of how far a function is from being a simple linear combination of its inputs. High nonlinearity protects against linear cryptanalysis. The mathematical "gold standard" for nonlinearity is the bent function, which achieves the maximum possible distance from all linear functions.
However, as Subhamoy Maitra explores in Minimum Distance between Bent and 1-resilient Boolean Functions, bent functions are inherently flawed for many applications: they are unbalanced (outputting more 0s than 1s) and lack resiliency. Resiliency is crucial for stream ciphers to prevent correlation attacks, which exploit statistical dependencies between the cipher's internal state and its output.
The challenge is that the constraints for high nonlinearity and high resiliency are mathematically at odds. Subhamoy Maitra has demonstrated that while record-breaking nonlinearity can be achieved in balanced functions—such as in the 13-variable case Balanced Boolean Function on 13-variables having Nonlinearity strictly greater than the Bent Concatenation Bound—maintaining this balance while increasing resiliency typically forces a reduction in nonlinearity.
Algebraic Immunity and the Resistance Ceiling
Beyond linear attacks, ciphers must resist algebraic attacks, which attempt to solve systems of polynomial equations to recover keys. This resistance is measured by Algebraic Immunity (AI).
Research by Subhamoy Maitra in Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity highlights a persistent construction gap: even when the theoretical maximum for AI is known, finding functions that reach this limit while remaining balanced and highly nonlinear is difficult. Furthermore, Notion of Algebraic Immunity and Its evaluation Related to Fast Algebraic Attacks suggests that standard AI is not enough; functions must also resist "fast" algebraic attacks, a requirement that often imposes a ceiling on other cryptographic properties like the algebraic degree.
Hardware Efficiency vs. Security Margins
In the realm of IoT and RFID tags, security must be "lightweight." Designers like Axel Pöschmann and San Ling have shown that even older standards like GOST can be optimized to fit into tiny hardware footprints (as few as 651 Gate Equivalents) by using serialized architectures 256 Bit Standardized Crypto for 650 GE - GOST Revisited.
However, efficiency often introduces new vulnerabilities. For example, the quest for ultra-low energy in the Midori64 cipher inadvertently allowed for invariant subspace attacks, as detailed by Jian Guo and colleagues Invariant Subspace Attack Against Midori64 and The Resistance Criteria for S-box Designs. Similarly, protecting hardware against power-analysis attacks using Threshold Implementations requires S-boxes to be decomposable into quadratic functions—a structural constraint that many mathematically "optimal" S-boxes do not satisfy On 3-share Threshold Implementations for 4-bit S-boxes.
Navigating the Search Space with Evolutionary Algorithms
Because the space of possible Boolean functions is astronomically large ($2^{2^n}$ for $n$ variables), and the "good" functions are rare "needles in a haystack," researchers have increasingly turned to metaheuristics.
Claude Carlet, Domagoj Jakobović, and Stjepan Picek have pioneered the use of Evolutionary Algorithms (EAs) to discover functions with rare combinations of properties, such as being bent, rotation symmetric, and self-dual Discovering Rotation Symmetric Self-dual Bent Functions with Evolutionary Algorithms.
These automated searches reveal a hierarchy of difficulty among cryptographic metrics. For instance, Marko Ðurasević and Luca Mariot found that boomerang uniformity (resistance to boomerang attacks) is significantly harder to optimize than traditional differential uniformity On the Evolution of Boomerang Uniformity in Cryptographic S-boxes. This suggests that the fitness landscape for certain security properties is more "rugged" and constrained, requiring multi-objective optimization to find the best possible trade-offs on the Pareto front.