Algebraic aspects of symmetric cryptography

Abstract

Classical symmetric cryptography interprets ciphers and hash functions as bit-based functions, that is, as functions between binary vector spaces. However, in the past decade, research and adoption of cryptographic protocols with advanced privacy-enhancing features, such as Fully Homomorphic Encryption, Multi-Party Computation and Zero-Knowledge proof systems, have accelerated. These privacy-enhancing protocols often have a novel feature: Their mathematical model is native over a prime field, whose characteristic p is significantly larger than 2. Applications of the aforementioned protocols often require a symmetric cipher for data encryption or a hash function for data compression. For efficiency reasons, two novel criteria must be satisfied: - A primitive should be native over a prime field, so it is modeled as function between vector spaces of characteristic p. - It should be possible to evaluate or represent a primitive with a low number of multiplications. Primitives satisfying these criteria are often summarized under the term Arithmetization-Oriented. To satisfy the second criterion, Arithmetization-Oriented primitives are often constructed by iterating relatively low-degree polynomials. However, this choice comes at a cost: Such primitive can also be modeled as a low-degree polynomial system for key or preimage recovery. Analyzing the complexity of polynomial system solving-based attacks poses a major problem in the design of Arithmetization-Oriented primitives. In practice, cryptodesigners often applied generic complexity bounds for cryptanalysis without proving the underlying assumptions. The aim of this manuscript is the development of tools for complexity estimations based on provable properties of a cryptographic polynomial system. We also apply our tools to the analysis of Arithmetization-Oriented Substitution-Permutation Network and Feistel ciphers. For early Arithmetization-Oriented primitives, our analysis reveals a large complexity gap between initial cryptanalysis and the capabilities of state-of-the-art polynomial system solving techniques.