Category: Uncategorized

Lors de cet exposé, une revue de plusieurs résultats sur la résolution algébrique sera présentée.

Je montrerai comment l’utilisation des structures des données en entrée permet, dans certains cas, d’accélérer le processus de résolution.
Les problématiques traitées seront liées au calcul des racines d’un polynôme en une variable (théorie de Galois) à la recherche de ses racines entières (problèmes diophantiens) et la résolution de systèmes polynomiaux.

Une part importante de l’exposé portera sur les applications de ces résultats en cryptanalyse.

Counting the number of points of an algebraic variety over a finite field, or equivalently computing its so called zeta function, is a central problem in computational number theory with applications to cryptography and coding theory. For elliptic curves and some curves of genus 2, variants of Schoof’s polynomial time algorithm can be used. For more general varieties, the best available algorithms are based on p-adic cohomology. Building on work of Kedlaya, Lauder and Harvey, over the past years we have obtained some of the best and most general algorithms of this type. The talk will give an overview of some of the recent work in this area and will be aimed at a rather general audience.

On étudie une méthode de type GLV en dimension 4, basée sur des familles de Q-courbes avec un endomorphisme CM de petit degré. Par exemple, la courbe FourQ, proposée par Costello et Longa (Microsoft) et apportant 127 bits de sécurité, utilise cette méthode pour calculer efficacement [k]P. Afin d’étendre la proposition de Costello et Longa pour d’autres niveaux de sécurité, on développe des outils de recherche systématique de courbes et de construction des endomorphismes associés.

Nous obtenons une courbe apportant 254 bits de sécurité, possédant un endomorphisme agissant comme \sqrt{2} ainsi qu’un endomorphisme CM agissant comme \sqrt{-11} sur le groupe des points E(\mathbb{F}_{p^2}). On explicite et simplifie les expressions de ces endomorphismes. Le corps de définition de cette courbe possède une arithmétique efficace bien connue, qui permet d’accélérer à nouveau la multiplication scalaire.

The Rényi divergence is a measure of divergence between distributions. It has recently found several applications in lattice-based cryptography. The contribution of this paper is twofold. First, we give theoretic results which renders it more efficient and easier to use. This is done by providing two lemmas, which give tight bounds in very common situations – for distributions that are tailcut or have a bounded relative error. We then connect the Rényi divergence to the max-log distance. This allows the Rényi divergence to indirectly benefit from all the advantages of a distance. Second, we apply our new results to five practical usecases. It allows us to claim 256 bits of security for a floating-point precision of 53 bits, in cases that until now either required more than 150 bits of precision or were limited to 100 bits of security: rejection sampling, trapdoor sampling (61 bits in this case) and a new sampler by Micciancio and Walter. We also propose a new and compact approach for table-based sampling, and squeeze the standard deviation of trapdoor samplers by a factor that provides a gain of 30 bits of security in practice.

Supersingular-isogeny Diffie-Hellman (SIDH) is an attractive candidate for post-quantum key exchange, in large part due to its relatively small public key sizes. A recent paper showed that the public keys in the original SIDH scheme can be further compressed by around a factor of two, but reported that the performance penalty in utilizing this compression blew the overall SIDH runtime out by more than an order of magnitude. Given that the runtime of SIDH key exchange is currently its main drawback in relation to its lattice- and code-based post-quantum alternatives, an order of magnitude performance penalty for a factor of two improvement in bandwidth presents a trade-off that is unlikely to favor public-key compression in many scenarios.
This talk will introduce algorithms and techniques that accelerate SIDH public-key-compression by more than an order of magnitude, making it roughly as fast as a round of standalone SIDH key exchange, while further reducing the size of the compressed public keys by 12.5%. These improvements enable the practical use of compression, achieving public keys of only 330 bytes for the concrete parameters used to target 128 bits of quantum security and further strengthens SIDH as a promising post-quantum primitive.

We describe a subquadratic algorithm for systematic encoding of multiplicity codes. These codes generalise the construction of Reed-Muller codes by additionally evaluating partial derivatives, allowing higher rates to be obtained while retaining sublinear local decoding. We base our encoding algorithm upon the multivariate interpolation and evaluation algorithms of van der Hoeven and Schost (2013), which we partially generalise to handle the presence of derivatives.