Abstract
The security of the Advanced Encryption Standard (AES) relies heavily on the nonlinear properties of its S-box. While traditional analysis focuses on Boolean (bit-level) nonlinearity, this paper explores the S-box's performance within many-valued logic systems, specifically 4-valued and 16-valued logic. By employing the Vilenkin-Chrestenson transform and a novel recursive matrix construction method, the authors demonstrate that the choice of irreducible polynomial significantly impacts higher-order nonlinearity, despite Boolean nonlinearity remaining constant. The study identifies optimal polynomials that maximize cryptographic strength across multiple logic bases.
Introduction
In symmetric cryptography, Substitution-boxes (S-boxes) are critical components designed to provide "confusion" by obscuring the relationship between the plaintext and the ciphertext. The Rijndael S-box, central to the AES standard, is constructed using the Nyberg method, which involves finding the multiplicative inverse in the finite field $GF(2^8)$. Traditionally, the quality of an S-box is measured by its nonlinearity—the degree to which it deviates from a linear function—calculated using Boolean logic. However, this approach may overlook vulnerabilities detectable through many-valued logic analysis.
The Many-Valued Logic Perspective
Standard cryptanalysis often treats data as a sequence of bits. Yet, an attacker might analyze an S-box by looking at larger data chunks, such as nibbles (4 bits) or bytes (8 bits), corresponding to 16-valued or 256-valued logic. The authors argue that understanding how the mathematical foundation of the finite field—specifically the choice of the irreducible polynomial—affects these higher-order properties is essential for robust security.
Methods and the Vilenkin-Chrestenson Transform
To evaluate nonlinearity in higher bases ($q > 2$), the researchers utilize the Vilenkin-Chrestenson transform, the many-valued analogue of the Walsh-Hadamard transform. A significant technical contribution of this work is a new recursive formula for constructing hexadecimal Vilenkin-Chrestenson matrices ($V_{16}$).
This recursive approach simplifies the computation of nonlinearity for S-boxes of length $N=256$. By treating the S-box as a set of component $q$-functions, the authors can systematically measure how much the S-box deviates from linear functions in bases 4 and 16.
Datasets: The Rijndael S-box
The primary object of study is the Rijndael S-box itself, typically represented as a lookup table.
The researchers analyzed 30 different irreducible polynomials of degree 8 over $GF(2)$ used to construct such S-boxes. While the standard AES S-box uses the polynomial $283_{10}$, the study explores whether alternative polynomials offer better resistance to many-valued logic attacks.
Key Insights and Results
The most significant finding is the "Hidden Variance" in nonlinearity. For all 30 tested polynomials, the Boolean nonlinearity ($2N_S$) remained a constant 112. However, when analyzed in 4-valued and 16-valued logic, the nonlinearity values fluctuated significantly:
- Quaternary (4-valued): Nonlinearity varied between 210 and 221.
- Hexadecimal (16-valued): Nonlinearity varied between 200 and 220.
The authors identified polynomial $f_{28} = 499_{10}$ as an "optimal" choice. It provides high nonlinearity in both 4-valued and 16-valued systems while minimizing the correlation between input and output vectors, making it a superior candidate for practical cryptographic implementations.
Conclusion
This research highlights that the choice of irreducible polynomial in S-box construction is more consequential than previously thought. By introducing an efficient recursive method for many-valued logic analysis, the authors provide a new framework for evaluating cryptographic primitives. Future work should focus on applying these methods to other S-box designs and investigating potential practical attacks that exploit variances in many-valued nonlinearity.
Summary updated