Academic literature on the topic 'Arithmetization-Oriented'

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.

Hash functions are a crucial component in incrementally verifiable computation (IVC) protocols and applications. Among those, recursive SNARKs and folding schemes require hash functions to be both fast in native CPU computations and compact in algebraic descriptions (constraints). However, neither SHA-2/3 nor newer algebraic constructions, such as Poseidon, achieve both requirements. In this work we overcome this problem in several steps. First, for certain prime field domains we propose a new design strategy called Kintsugi, which explains how to construct nonlinear layers of high algebraic degree which allow fast native implementations and at the same time also an efficient circuit description for zeroknowledge applications. Then we suggest another layer, based on the Feistel Type-3 scheme, and prove wide trail bounds for its combination with an MDS matrix. We propose a new permutation design named Monolith to be used as a sponge or compression function. It is the first arithmetization-oriented function with a native performance comparable to SHA3-256. At the same time, it outperforms Poseidon in a circuit using the Merkle tree prover in the Plonky2 framework. Contrary to previously proposed designs, Monolith also allows for efficient constant-time native implementations which mitigates the risk of side-channel attacks.

For Arithmetization-Oriented ciphers and hash functions Gröbner basis attacks are generally considered as the most competitive attack vector. Unfortunately, the complexity of Gröbner basis algorithms is only understood for special cases, and it is needless to say that these cases do not apply to most cryptographic polynomial systems. Therefore, cryptographers have to resort to experiments, extrapolations and hypotheses to assess the security of their designs. One established measure to quantify the complexity of linear algebra-based Gröbner basis algorithms is the so-called solving degree. Caminata & Gorla revealed that under a certain genericity condition on a polynomial system the solving degree is always upper bounded by the Castelnuovo-Mumford regularity and henceforth by the Macaulay bound, which only takes the degrees and number of variables of the input polynomials into account. In this paper we extend their framework to iterated polynomial systems, the standard polynomial model for symmetric ciphers and hash functions. In particular, we prove solving degree bounds for various attacks on MiMC, Feistel-MiMC, Feistel-MiMC-Hash, Hades and GMiMC. Our bounds fall in line with the hypothesized complexity of Gröbner basis attacks on these designs, and to the best of our knowledge this is the first time that a mathematical proof for these complexities is provided. Moreover, by studying polynomials with degree falls we can prove lower bounds on the Castelnuovo-Mumford regularity for attacks on MiMC, Feistel-MiMC and Feistel-MiMCHash provided that only a few solutions of the corresponding iterated polynomial system originate from the base field. Hence, regularity-based solving degree estimations can never surpass a certain threshold, a desirable property for cryptographic polynomial systems.

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.

AbstractRecently, many cryptographic primitives such as homomorphic encryption (HE), multi-party computation (MPC) and zero-knowledge (ZK) protocols have been proposed in the literature which operate on the prime field $${\mathbb {F}}_p$$ F p for some large prime p. Primitives that are designed using such operations are called arithmetization-oriented primitives. As the concept of arithmetization-oriented primitives is new, a rigorous cryptanalysis of such primitives is yet to be done. In this paper, we investigate arithmetization-oriented APN functions. More precisely, we investigate APN permutations in the CCZ-classes of known families of APN power functions over the prime field $${\mathbb {F}}_p$$ F p . Moreover, we present a class of binomial permutation having differential uniformity at most 5 defined via the quadratic character over finite fields of odd characteristic. Computationally it is confirmed that the latter family contains new APN permutations for some small parameters. We conjecture it to contain an infinite subfamily of APN permutations.

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.

La cryptographie joue un rôle clé dans la communication numérique, en garantissant que les utilisateurs malveillants ne peuvent pas obtenir des informations sensibles qui ne leur appartiennent pas. En cryptographie symétrique, deux utilisateurs conviennent d'une clé secrète et utilisent un moyen de chiffrement pour communiquer, le plus utilisé étant l'AES. La sécurité des chiffrements symétriques n'est cependant pas mathématiquement prouvable, donc beaucoup d'efforts doivent être consacrés à la cryptanalyse, c'est-à-dire à la recherche des meilleures attaques.Dans ce contexte, cette thèse améliore certaines techniques de cryptanalyse contre les chiffrements basés sur l'AES. Tout d'abord, nous présentons une attaque sur la version complète de ForkAES, et améliorons les attaques différentielles impossibles sur ForkSkinny. Ensuite, nous montrons de nouvelles attaques boomerang sur 6 tours d'AES et sur plusieurs primitives basées sur l'AES. En particulier, nous introduisons un nouveau framework d'attaques boomerangs, l'attaque boomerang tronquée, dont on dérive les meilleures attaques connues contre Kiasu-BC, Deoxys-BC et TNT-AES.Nous présentons également un framework de fonctions de hachage universelles basées sur l'AES, à partir duquel nous concevons deux MACs basés sur AES, LeMac et PetitMac. LeMac offre les meilleures performances logicielles sur des processeurs récents, parmi les MACs existants.Enfin, nous étudions les attaques algébriques contre une nouvelle génération de primitives symétriques, appelées Arithmétisation-Orientées (AO). Nous montrons que ces attaques peuvent être améliorées avec des techniques symétriques, et soulignons que les attaques univariées sont beaucoup moins coûteuses que les attaques multivariées. Nous présentons également l'attaque FreeLunch, un nouveau type d'attaque algébrique qui remet en question la sécurité de plusieurs primitives AO récentes
Cryptography plays a critical role in digital communication, by ensuring that malicious users cannot obtain sensitive information that do not belong to them. In symmetric cryptography, two parties agree on a secret key, and use a cipher to encrypt their communication, the most used of which being AES. However, the security of symmetric ciphers is not mathematically provable, therefore a lot of effort needs to be dedicated to cryptanalysis, i.e. the search for the best attacks.In this context, this thesis improves on some cryptanalysis techniques against AES-based ciphers. First, we present an attack on full ForkAES, together with an improved impossible differential attack on ForkSkinny. Second, we show some new boomerang attacks on 6-round AES and on several AES-based ciphers. In particular, we introduce a new boomerang attack framework, the truncated boomerang attack, that yields the best known attacks against Kiasu-BC, Deoxys-BC and TNT-AES.We also present an AES-based universal hash function framework, from which we design two AES-based MACs, LeMac and PetitMac. LeMac offers the best software performance among existing MAC algorithms on recent desktop CPUs.We finally study algebraic attacks against a new generation of symmetric primitives, called Arithmetization-Oriented (AO). We show that these attacks can be improved with symmetric techniques, and highlight that univariate attacks are much cheaper than multivariate attacks. We also present the FreeLunch attack, a new type of algebraic attack that challenges the security of several recent AO primitives

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