Exposés au séminaire C2 du vendredi 10 juin 2022
- Clara Pernot, INRIA Paris, New Representations of the AES Key Schedule
Résumé : In this talk we present a new representation of the AES key schedule, with some implications to the security of AES-based schemes. In particular, we show that the AES-128 key schedule can be split into four independent parallel computations operating on 32 bits chunks, up to linear transformation. Surprisingly, this property has not been described in the literature after more than 20 years of analysis of AES. We show two consequences of our new representation, improving previous cryptanalysis results of AES-based schemes. First, we observe that iterating an odd number of key schedule rounds results in a function with short cycles. This explains an observation of Khairallah on mixFeed, a second-round candidate in the NIST lightweight competition. Our analysis actually shows that his forgery attack on mixFeed succeeds with probability 0.44 (with data complexity 220GB), breaking the scheme in practice. The same observation also leads to a novel attack on ALE, another AES-based AEAD scheme.
Our new representation also gives efficient ways to combine information from the first subkeys and information from the last subkeys, in order to reconstruct the corresponding master keys. In particular we improve previous impossible differential attacks against AES-128.
This is a joint work with Gaëtan Leurent.
- Thibauld Feneuil, CryptoExperts et Sorbonne Université – Syndrome Decoding in the Head – Shorter Signatures from Zero-Knowledge proofs
Résumé : In this talk, I will present a new zero-knowledge proof of knowledge for the syndrome decoding (SD) problem on random linear codes. Instead of using permutations like most of the existing protocols, we rely on the MPC-in-the-head paradigm in which we reduce the task of proving the low Hamming weight of the SD solution to proving some relations between specific polynomials. Specifically, we propose a 5-round zero-knowledge protocol that proves the knowledge of a vector x such that y=Hx and wt(x)<= w and which achieves a soundness error closed to 1/N for an arbitrary N.
While turning this protocol into a signature scheme, we achieve a signature size of 11-12 KB for 128-bit security when relying on the hardness of the SD problem on binary fields. Using larger fields (like F_{256}), we can produce fast signatures of around 8 KB. This allows us to outperform Picnic3 and to be competitive with SPHINCS+, both post-quantum signature candidates in the ongoing NIST standardization effort. Since the security relies on the hardness of the syndrome decoding problem for random linear codes which is known to be NP-hard and for which the cryptanalysis state of the art has been stable for many years, it results in a conservative signature scheme. Moreover, our scheme outperforms all the existing code-based signature schemes for the common « signature size + public key size » metric.
Joint work with Antoine Joux and Matthieu Rivain.
- Fangan Yssouf Dosso, Ecole des Mines de Saint-Etienne, Département SAS – PMNS for efficient arithmetic and small memory cost
Résumé : The Polynomial Modular Number System (PMNS) is an integer number system which aims to speed up arithmetic operations modulo a prime p. Such a system is defined by a tuple (p, n, g, r, E), where p, n, g and r are positive integers, E is a monic polynomial with integer coefficients, having g as a root modulo p. Most of the work done on PMNS focus on polynomials E such that E(X) = X^n – l, where l is a nonzero integer, because such a polynomial provides efficiency and low memory cost, in particular for l = 2 or -2.
It however appeared that these are not always the best choices. In this presentation, we first start with the necessary background on PMNS. Then, we highlight a new set of polynomials E for very efficient operations in the PMNS and low memory requirement, along with new bounds and parameters. We show that these polynomials are more interesting than (most) polynomials E(X)=X^n – l. To finish, we see how to use PMNS to randomise arithmetic operations in order to randomise high level operations like elliptic curve scalar multiplication, to protect implementations against some advanced side channel attacks like differential power analysis (DPA).
Joint work with Jean-Marc Robert, Nadia EL MRABET, Laurent-Stéphane DIDIER et Pascal Véron
- Ivan Pogildiakov, IRMAR, Université Rennes 1 – Binary codes, hyperelliptic curves, and the Serre bound
Résumé : Algebraic curves over finite fields have found nice applications in such areas as Coding theory and Cryptography. In that context, an object of this sort is meaningful only if its number of rational points is as close as possible to the celebrated Serre bound. However, the question regarding the existence of an algebraic curve having a prescribed number of rational points is of theoretical interest in its own right. There are different types of results in this direction in the literature such as, for example, providing explicit or non-explicit constructions in the case when either the definition field, or the genus, or the number of rational points varies.
In this talk, we propose a new approach for constructions of hyperelliptic curves over a fixed finite field of odd characteristic. As a main tool, a specific binary linear code defined by the field is used. A nice feature of the approach is that it allows one to translate the existence and the search problems of a hyperelliptic curve having desired parameters to that of a codeword of corresponding Hamming weight in a coset of the linear code. In some cases, by means of the machinery of the general theory of linear codes, we manage to find curves (having a fixed number of rational points) whose genera are reasonably close to the Serre bound.
For the sake of simplicity, the case of prime fields is mainly discussed. If time permits, as a by-product result, we will obtain new examples of curves with many points that improve upon some known lower bounds.
