TL;DR
This paper introduces a novel theoretical construction for Rotation Symmetric Boolean Functions (RSBFs) on an odd number of variables that achieve maximum algebraic immunity. These new RSBFs offer better nonlinearity than existing constructions, a crucial property for secure cryptographic designs.
What Problem Does This Paper Address?
In cryptography, particularly for stream and block ciphers, resisting algebraic attacks is paramount. A key metric for this resistance is algebraic immunity (AI). For an n-variable Boolean function, the maximum possible AI is $\lfloor n/2 \rfloor$. While many constructions exist for Boolean functions with maximum AI, achieving this while also maintaining desirable properties like nonlinearity and rotational symmetry is challenging.
Rotational Symmetry is a desirable property because it leads to more compact representations and has been linked to good cryptographic characteristics. However, known constructions for RSBFs with maximum AI were limited. Specifically, for an odd number of variables, only the majority function was known to be a symmetric Boolean function with maximum AI. This paper aims to bridge this gap by providing a theoretical construction for RSBFs with maximum AI that are not symmetric, and crucially, exhibit improved nonlinearity.
Methods
The paper proposes a series of constructions for RSBFs with maximum AI.
- Construction 1: This is the core theoretical construction. It starts with the n-variable majority function (which has maximum AI) and toggles the outputs for specific inputs belonging to two carefully chosen orbits. The key is that these orbits are selected such that a related sub-matrix is nonsingular, which is a condition for maintaining maximum AI. This construction generates RSBFs that are not symmetric.
- Construction 2 & 3: These are generalizations of Construction 1, relaxing some of the initial constraints on orbit selection. This allows for a broader class of RSBFs and, importantly, leads to improved nonlinearity.
- Heuristic Search: To find RSBFs with even better nonlinearity, the authors combine their constructions with a limited search strategy. This involves starting with a constructed RSBF, choosing two orbits with different output values, toggling their outputs, and checking if the resulting function still has maximum AI and improved nonlinearity.
The theoretical underpinnings involve concepts like algebraic normal form (ANF), Walsh spectrum, and the use of matrices (specifically, the $M_{n,d}(f)$ matrix and the $W$ matrix) to analyze algebraic immunity and nonsingularity.
Datasets
Not discussed in the paper. The paper focuses on theoretical constructions and analysis rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Breaking Symmetry for Better Performance: The paper demonstrates that by strategically breaking the symmetry of the majority function, one can obtain RSBFs with maximum AI and significantly improved nonlinearity. This is a crucial insight for cryptographic design, as nonlinearity is vital for resisting differential and linear cryptanalysis.
- The Power of Orbit Manipulation: The core idea of toggling outputs based on carefully selected orbits is a powerful technique. The paper shows how the properties of these orbits (specifically, their relationship through the Walsh spectrum and matrix analysis) directly influence the resulting function's AI and nonlinearity.
- Bridging Theory and Practice: The combination of theoretical constructions with a limited search heuristic is a practical approach. It allows for the discovery of high-performing functions without requiring exhaustive searches, which are computationally infeasible for larger numbers of variables.
- Nonlinearity Beyond the Lower Bound: A significant finding is that the constructed RSBFs achieve nonlinearities that are not just at the theoretical lower bound but exceed it, offering a tangible improvement for cryptographic security.
Key Results
- Construction 1: Generates RSBFs on odd variables ($n \ge 5$) with maximum AI that are not symmetric.
- Nonlinearity Improvement: The RSBFs from Construction 1 achieve a nonlinearity of $2^{n-1} - \lfloor n/2 \rfloor + 2$, which is 2 more than the known lower bound for such functions.
- Heuristic Search Results: The heuristic search, combined with the constructions, yielded 7, 9, and 11-variable RSBFs with maximum AI and nonlinearities of 56, 240, and 984, respectively. These values are close to or exceed $2^{n-1} - 2^{\lfloor n/2 \rfloor}$.
Limitations and Future Work
- Focus on Odd Variables: The current constructions are primarily for an odd number of variables. The authors mention that with minor modifications, the method could work for even variables, which is an area for future work.
- Search Heuristic: While the heuristic search is effective, the paper suggests that further work on better search heuristics is ongoing to discover RSBFs with even higher nonlinearities.
- Computational Complexity: The theoretical analysis, particularly the matrix operations for checking nonsingularity, can be computationally intensive for larger values of n. The paper acknowledges this and suggests methods to mitigate it, but it remains a practical consideration.
Summary updated