Abstract
Cryptographic Boolean functions are essential components of modern ciphers, requiring specific properties like high nonlinearity and balancedness to ensure security. Traditionally, these functions are evolved using their Truth Table (TT) representation. This paper explores an alternative approach: evolving functions directly in their Algebraic Normal Form (ANF). Our results show that ANF-based bitstring representations, especially when combined with local search, outperform traditional methods for large input sizes, reaching or improving upon previously known best results for functions with up to 16 inputs.
Introduction
In the design of block and stream ciphers, Boolean functions must satisfy several criteria to resist cryptanalytic attacks. Key properties include balancedness (an equal distribution of 0s and 1s), high nonlinearity (to thwart linear cryptanalysis), and a high algebraic degree (to resist algebraic attacks). For decades, metaheuristics such as Genetic Algorithms (GA) and Genetic Programming (GP) have been employed to search for functions meeting these criteria. However, the choice of representation—how the function is encoded for the algorithm—is critical. While Truth Tables are the standard, they may not align well with the algebraic properties being optimized. This study investigates whether the Algebraic Normal Form (ANF) offers a more effective search space.
Methodology
The research compares two primary encoding strategies within evolutionary frameworks:
- Bitstring Encoding (BS): Individuals are represented as bitstrings corresponding to the coefficients of the ANF polynomial. This is contrasted with the standard TT-based bitstring.
- Symbolic Encoding (GP): Functions are represented as trees of Boolean operators (e.g., AND, XOR). These trees are evaluated to generate a Truth Table, which is then converted to ANF for fitness assessment.
The evolutionary process utilized a Steady-state Genetic Algorithm with 3-tournament selection. To enhance performance, Memetic Algorithms were implemented by integrating Local Search (LS) techniques, such as mutation-based and exhaustive bit-flip operators, to refine candidate solutions. Two distinct fitness functions were tested: one focusing solely on balancedness and nonlinearity, and a second that explicitly incorporated the algebraic degree.
Results
The performance of these methods was evaluated across 13 input sizes ($n=4$ to $n=16$). Random Search (RS) served as a baseline.
As shown in Table 1, all methods successfully found optimal solutions for small $n$ (4-6). For medium sizes like $n=8$, the combination of GP and Local Search achieved a nonlinearity of 116, a significant benchmark in the field.
Table 2 highlights the impact of including the algebraic degree in the fitness objective. Interestingly, for larger $n$, this inclusion facilitated the discovery of functions with even higher nonlinearity. For instance, at $n=16$, the BS-L approach reached a value of 32344, surpassing the 32327 achieved without the algebraic degree objective.
Discussion
Several key insights emerged from the experiments:
- Representation Fit: The ANF representation is inherently better suited for bitstring-based GAs than the Truth Table. ANF-based evolution consistently outperformed TT-based approaches in most scenarios.
- Scaling and Hybridization: While Genetic Programming excels for smaller functions ($n \leq 9$), bitstring-based GAs combined with Local Search are more effective as the number of inputs increases ($n > 10$).
- Structural Synergy: The ANF representation appears to expose structural relationships between nonlinearity and algebraic degree that are obscured in the TT representation. This synergy allows the algorithm to exploit one property to improve the other.
- Initial Population Quality: Even random solutions in the ANF space tend to have better initial nonlinearity than those in the TT space, providing a more favorable starting point for evolution.
Conclusion
This work demonstrates that the Algebraic Normal Form is a powerful representation for the evolutionary design of cryptographic Boolean functions. By leveraging ANF-based bitstrings and local search, researchers can find high-quality functions for large input sizes that were previously difficult to reach. Future research may explore the Numerical Normal Form (NNF) to further expand the search capabilities of evolutionary algorithms in this domain.
Summary updated