Academic literature on the topic 'Arithmetization-oriented primitives'

The rise of modern cryptographic protocols such as Zero-Knowledge proofs and secure Multi-party Computation has led to an increased demand for a new class of symmetric primitives. Unlike traditional platforms such as servers, microcontrollers, and desktop computers, these primitives are designed to be implemented in arithmetical circuits. In terms of security evaluation, arithmetization-oriented primitives are more complex compared to traditional symmetric cryptographic primitives. The arithmetization-oriented permutation Grendel employs the Legendre Symbol to increase the growth of algebraic degrees in its nonlinear layer. To analyze the security of Grendel thoroughly, it is crucial to investigate its resilience against algebraic attacks. This paper presents a preimage attack on the sponge hash function instantiated with the complete rounds of the Grendel permutation, employing algebraic methods. A technique is introduced that enables the elimination of two complete rounds of substitution permutation networks (SPN) in the sponge hash function without significant additional cost. This method can be combined with univariate root-finding techniques and Gröbner basis attacks to break the number of rounds claimed by the designers. By employing this strategy, our attack achieves a gain of two additional rounds compared to the previous state-of-the-art attack. With no compromise to its security margin, this approach deepens our understanding of the design and analysis of such cryptographic primitives.

Motivated by progress in the field of zero-knowledge proofs, so-called Arithmetization-Oriented (AO) symmetric primitives have started to appear in the literature, such as MiMC, Poseidon or Rescue. Due to the design constraints implied by this setting, these algorithms are defined using simple operations over large (possibly prime) fields. In particular, many rely on simple low-degree monomials for their non-linear layers, essentially using x ↦ x3 as an S-box.In this paper, we show that the structure of the material injected in each round (be it subkeys in a block cipher or round constants in a public permutation) could allow a specific pattern, whereby a well-defined affine space is mapped to another by the round function, and then to another, etc. Such chains of one-dimensional subspaces always exist over 2 rounds, and they can be extended to an arbitrary number of rounds, for any linear layer, provided that the round-constants are well chosen.As a consequence, for several ciphers like Rescue, or a variant of AES with a monomial Sbox, there exist some round-key sequences for which the cipher has an abnormally high differential uniformity, exceeding the size of the Sbox alphabet.Well-known security arguments, in particular based on the wide-trail strategy, have been reused in the AO setting by many designers. Unfortunately, our results show that such a traditional study may not be sufficient to guarantee security. To illustrate this, we present two new primitives (the tweakable block cipher Snare and the permutation-based hash function Stir) that are built using state-of-the-art security arguments, but which are actually deeply flawed. Indeed, the key schedule of Snare ensures the presence of a subspace chain that significantly simplifies an algebraic attack against it, and the round constants of Stir force the presence of a subspace chain aligned with the rate and capacity of the permutation. This in turns implies the existence of many easy-to-find solutions to the so-called CICO problem.

Recent advanced Zero-Knowledge protocols, along with other high-level constructions such as Multi-Party Computations (MPC), have highlighted the need for a new type of symmetric primitives that are not optimized for speed on the usual platforms (desktop computers, servers, microcontrollers, RFID tags...), but for their ability to be implemented using arithmetic circuits.Several primitives have already been proposed to satisfy this need. In order to enable an efficient arithmetization, they operate over large finite fields, and use round functions that can be modelled using low degree equations. The impact of these properties on their security remains to be completely assessed. In particular, algebraic attacks relying on polynomial root-finding become extremely relevant. Such attacks work by writing the cryptanalysis as systems of polynomial equations over the large field, and solving them with off-the-shelf tools (SageMath, NTL, Magma, . . . ).The need for further analysis of these new designs has been recently highlighted by the Ethereum Foundation, as it issued bounties for successful attacks against round-reduced versions of several of them.In this paper, we show that the security analysis performed by the designers (or challenge authors) of four such primitives is too optimistic, and that it is possible to improve algebraic attacks using insights gathered from a careful study of the round function.First, we show that univariate polynomial root-finding can be of great relevance n practice, as it allows us to solve many of the Ethereum Foundation’s challenges on Feistel–MiMC. Second, we introduce a trick to essentially shave off two full rounds at little to no cost for Substitution-Permutation Networks (SPN). This can be combined with univariate (resp. multivariate) root-finding, which allowed to solve some challenges for Poseidon (resp. Rescue–Prime). Finally, we also find an alternative way to set up a system of equations to attack Ciminion, leading to much faster attacks than expected by the designers.

While traditional symmetric algorithms like AES and SHA-3 are optimized for efficient hardware and software implementations, a range of emerging applications using advanced cryptographic protocols such as multi-party computation and zero knowledge proofs require optimization with respect to a different metric: arithmetic complexity.In this paper we study the design of secure cryptographic algorithms optimized to minimize this metric. We begin by identifying the differences in the design space between such arithmetization-oriented ciphers and traditional ones, with particular emphasis on the available tools, efficiency metrics, and relevant cryptanalysis. This discussion highlights a crucial point—the considerations for designing arithmetization-oriented ciphers are oftentimes different from the considerations arising in the design of software- and hardware-oriented ciphers.The natural next step is to identify sound principles to securely navigate this new terrain, and to materialize these principles into concrete designs. To this end, we present the Marvellous design strategy which provides a generic way to easily instantiate secure and efficient algorithms for this emerging domain. We then show two examples for families following this approach. These families — Vision and Rescue — are benchmarked with respect to three use cases: the ZK-STARK proof system, proof systems based on Rank-One Constraint Satisfaction (R1CS), and Multi-Party Computation (MPC). These benchmarks show that our algorithms achieve a highly compact algebraic description, and thus benefit the advanced cryptographic protocols that employ them.

Ces dernières années, de nouvelles primitives de cryptographie symétrique ont été proposées pour être utilisées dans des protocoles avancés comme le calcul multi-partite, en combinaison avec un chiffrement homomorphe ou encore dans divers systèmes de preuve à apport nul de connaissance. De tels protocoles s’inscrivent dans un contexte marqué par le développement du Cloud et des technologies de type Blockchain et doivent ainsi répondre à une préoccupation croissante des utilisateurs en matière de sécurité. Ces protocoles ont mis en avant le besoin de minimiser le nombre de multiplications effectuées par la primitive dans des corps finis de grande taille. Les algorithmes symétriques classiques sont alors inappropriés dans ce contexte et les nouveaux protocoles cryptographiques doivent être combinés avec des primitives symétriques (chiffrement ou fonction de hachage) ayant des propriétés particulières. Alors que le nombre de conceptions définies sur de grands corps dites "orientées arithmétisation" augmente de façon considérable, très peu de travaux d’analyse de sécurité ont été proposés jusqu'ici. L’objectif de ce manuscrit est donc en premier lieu de contribuer à combler ce manque pour mieux comprendre les spécificités de ces nouveaux outils. Nous proposons également une nouvelle vision pour concevoir de telles primitives, couvrant ainsi les deux sous-domaines de la cryptologie que sont la cryptographie et la cryptanalyse
In recent years, new symmetric cryptographic primitives have been proposed for advanced protocols, like multi-party computation, in combination with a fully homomorphic encryption or in various systems of zero-knowledge proofs. Such protocols are parts of a context marked by the development of cloud and blockchain technologies, and must therefore respond to the growing security concerns of users. These protocols have put forward the need to minimize the number of multiplications performed by the primitive in large finite fields. Classical symmetric algorithms are then inappropriate in this context and the new cryptographic protocols must be combined with symmetric primitives (encryption or hash function) with particular properties. While the number of designs defined over large fields, called "arithmetisation-oriented", is increasing significantly, few cryptanalysis works have been proposed. The first aim of this manuscript is then to contribute to fill this gap, and hence to better understand the specificities of these new objects. We also propose a new vision to design such primitives, covering both aspects of cryptology, the cryptography and the cryptanalysis