La prochaine édition du séminaire se tiendra le vendredi 27 janvier à ENS de Lyon, site Descartes, bâtiment D8 Buisson, salle D01.
L’entrée du bâtiment D8 Buisson se situe au 19 allée de Fontenay, 69007 Lyon, à 3 minutes de la station Debourg du métro B (ligne directe depuis la gare de Part-Dieu – le métro se situe à l’extérieur de la gare, côté centre-ville (il faut sortir du côté de la voie A). Un accueil se situe derrière la porte et l’entrée est visible depuis la salle D01 qui se situe juste en face.
-
- 10h45 : Johanna Loyer, INRIA Paris : Classical and quantum 3- and 4-sieves to solve SVP with low memory
Abstract: The Shortest Vector Problem (SVP) is at the foundation of lattice-based cryptography. The fastest known method to solve SVP in dimension d is by lattice sieving, which runs in time 2^{td+o(d)} with 2^{md+o(d)} memory for absolute constants t,m. Searching reduced vectors in the sieve is a problem reduced to the configuration problem, i.e. searching k vectors satisfying given constraints over their scalar products. In this work, we present a framework for k-sieve algorithms: we filter the input list of lattice vectors using a code structure modified from [BDGL16] to get lists centered around k codewords summing to the null-vector. Then, we solve a simpler instance of the configuration problem in the k filtered lists. Based on this framework, we describe classical sieves for k=3 and 4 that introduce new time-memory trade-offs. We also use the k-Lists algorithm [KPMP19] inside our framework, and this improves the time for k=3 and gives new trade-offs for k=4.
-
- 12h : Victor Dyseryn, XLIM,Université de Limoges – On the security of the PSSI problem and the Durandal signature scheme (joint work with Nicolas Aragon and Philippe Gaborit)
Abstract: The Product Spaces Subspaces Indistinguishability (PSSI) was presented at EUROCRYPT 2019 and is one of the pillars of the security of the Durandal signature scheme, which is an efficient rank-metric signature scheme introduced in the same 2019 paper. In this work we present a new attack against the PSSI problem. It combines signatures two by two to recover subspaces containing products of a secret scalar with a public scalar and then uses a chain of intersections to recover the secret key. This new attack is efficient against a wide range of parameters. In the case of EUROCRYPT 2019 Durandal parameters, it would allow the recovery of the secret key in about 2^36 attempts (plus costs of linear algebra), using only a few dozens of signatures. We then investigate how to mitigate this new attack and propose new secure parameters for the Durandal signature scheme.
-
- 14h30 : Bastien Pacifico, I2M, Aix-Marseille Université. Algorithmes de type Chudnovsky sur la droite projective pour la multiplication dans les corps finis.
Résumé : Il existe différents modèles permettant de mesurer la complexité d’un algorithme de multiplication dans une extension finie d’un corps fini.La complexité bilinéaire d’un tel algorithme est le nombre de multiplications bilinéaires, dépendant des deux éléments que l’on souhaite multiplier, qu’il exécute.La méthode de D.V. et G.V. Chudnovsky (1988) permet de construire des algorithmes ayant une bonne complexité bilinéaire. Ce sont des algorithmes d’évaluation/interpolation utilisant les points rationnels de courbes algébriques, i.e. les places rationnelles d’un corps de fonctions. Cette méthode a depuis été généralisée de différentes manières, et notamment à l’évaluation en des places de degrés arbitraires.Dans cet exposé, nous proposons une construction générique récursive d’algorithmes de type Chudnovsky sur le corps des fonctions rationnelles, évaluant sur des places de degrés croissants. Notre construction permet d’obtenir des algorithmes d’interpolation polynômiale constructibles en temps polynômial et ayant une complexité bilinéaire intéressante, pour un degré d’extension quelconque.D’autres part, nous verrons qu’il existe un profond lien entre ces algorithmes et les codes correcteurs d’erreurs géométriques.
Prépublication : https://arxiv.org/abs/2007.16082
-
- 15h45 : Benjamin Wesolowski, CNRS & ENS de Lyon- Hard problems for isogeny-based cryptography
Abstract: Isogeny-based cryptography is one of the few branches of public-key cryptography
that promises to resist quantum attacks. The security of these cryptosystems relates to the
(presumed) hardness of a variety of computational problems: finding paths in large « isogeny
graphs », computing endomorphisms of elliptic curves, or inverting group actions. We present
these problems, analyse their hardness, and discuss their applications to post-quantum
cryptography.
