Introduction
Modern symmetric ciphers are predominantly designed and analyzed using Boolean functions. While this binary approach has served the field well, it creates a "Boolean bias" that may overlook structural vulnerabilities. As cryptanalysts increasingly leverage many-valued logic (MVL) and quantum algorithms, there is a pressing need for a comprehensive framework to evaluate cryptographic quality beyond the bit-level. This paper explores the prerequisites for such a methodology, revealing hidden "cryptographic quality reserves" in standard algorithms.
Methodology for MVL-Based Evaluation
The proposed methodology extends traditional cryptographic criteria into the domain of $q$-valued logic ($q > 2$). The core of this approach involves decomposing S-boxes into component $q$-functions. For instance, an 8-bit S-box can be represented as eight Boolean functions, four 4-valued functions, or two 16-valued functions.
To facilitate comparisons across different logic bases, the authors introduced relative metrics:
- Relative Algebraic Degree: The degree expressed as a percentage of the maximum possible degree for a given base.
- Relative Nonlinearity: A comparison of a function's nonlinearity to that of "bent-functions" of the same length and base.
The analysis utilizes algebraic normal forms over Galois fields and Vilenkin-Chrestenson functions for spectral analysis. Furthermore, avalanche characteristics are assessed by measuring deviations from the Strict Avalanche Criterion (SAC).
Comparative Analysis of Block Cipher Standards
The methodology was applied to the S-boxes of four international standards: AES, Kalyna (Ukraine), BelT (Belarus), and Kuznechik (Russia). The results highlight significant differences in how these ciphers perform under MVL analysis.
A key finding is the "Weakest Link" principle: the overall quality of a cryptographic structure is dictated by its worst-performing MVL component. An S-box that appears optimal in Boolean terms may exhibit suboptimal properties in 4-valued or 16-valued logic.
As shown in Figure 2, the relative metrics for different ciphers diverge as the base $q$ increases. While all standards start at a similar baseline in Boolean logic ($q=2$), standards like BelT and Kuznechik demonstrate a more pronounced increase in their relative algebraic degree compared to AES and Kalyna as the logic base grows. This divergence suggests that certain ciphers possess a higher "cryptographic quality reserve" in higher-order logic representations that binary analysis fails to highlight.
Key Insights and Results
- Hidden Vulnerabilities: The analysis of Kalyna revealed a potential weakness in its confusion property, with nonlinearity metrics showing a relative decrease in certain MVL representations compared to Boolean analysis.
- SAC Deviations: While maximum deviations from SAC generally decreased with higher $q$ for AES-like ciphers, integral deviations increased. This indicates a complex trade-off in error propagation within higher-order logic structures.
- Quality Reserve: Many existing ciphers have untapped strength. By re-optimizing internal structures to satisfy MVL criteria, it is possible to increase cryptographic resistance without increasing computational overhead.
Conclusion and Future Work
This research establishes the foundational prerequisites for a formal MVL-based evaluation methodology. By identifying hidden weaknesses and quality reserves, it provides a roadmap for enhancing current block ciphers. Future work will focus on developing synthesis methods to build new cryptographic primitives that are optimized for both Boolean and many-valued logic, a critical step toward achieving post-quantum resilience.
Summary updated