Salle Jacques-Louis Lions 2, INRIA Paris, 2 rue Simone Iff, Paris 12ème, Métro Dugommier (ligne 6)
- 10h00, Yann Rotella, INRIA Paris : Attaques algébriques revisitées
La complexité de la résolution d’équations algébriques décrivant une primitive cryptographique est généralement difficile à évaluer mais reste cependant un problème fondamental pour les cryptographes. Depuis 2003, l’immunité algébrique est considérée comme le critère pertinent pour évaluer la sécurité des chiffrements symétriques au regard des attaques algébriques.
Au travers de quelques exemples de primitives cryptographiques telles que le PRG de Goldreich, le chiffrement à flot FLIP et les registres filtrés, nous investiguons de manière générale les possibilités que nous offrent des équations particulières. Plus précisément, nous montrons qu’il est possible d’exploiter le caractère creux des certaines équations algébriques, que la représentation soit multivariée ou univariée. Ceci nous permet de déterminer, selon le contexte, le critère à prendre en compte pour évaluer correctement la résistance de certains types de systèmes aux attaques algébriques.
- 11h30, Victor Cauchois, DGA et IRMAR : Constructions de matrices MDS pour la cryptographie.
Les matrices MDS ont été plébiscitées en cryptographie symétrique pour concevoir les couches de diffusion linéaires car elles assurent une diffusion minimale maximale sur les symboles. En vue d’implémentations matérielles légères, les matrices récursives et les matrices circulantes qui n’utilisent qu’un nombre linéaire de coefficients ont été largement explorées. Un résultat classique sur les corps de caractéristique 2 assure de plus qu’il n’existe pas de matrices circulantes involutives ni de matrices récursives involutives. Il est possible pourtant de « tordre » les définitions classiques de la récursivité, de la cyclicité et de l’involutivité pour construire des matrices MDS qui peuvent être implémentées au niveau matériel avec un nombre linéaire de multiplications dans un corps de Galois et avec une architecture presque identique pour réaliser la multiplication par la matrice ou par son inverse.
- 14h30, Alexandre Wallet, LIP, ENS Lyon : On the Ring-LWE and Polynomial-LWE problems.
The Ring Learning With Errors problem (RLWE) comes in various forms. Vanilla RLWE is the decision dual-RLWE variant, consisting in distinguishing from uniform a distribution depending on a secret belonging to the dual OK^vee of the ring of integers OK of a specified number field K. In primal-RLWE, the secret instead belongs to OK. Both decision dual-RLWE and primal-RLWE enjoy search counterparts. Also widely used is (search/decision) Polynomial Learning With Errors (PLWE), which is not defined using a ring of integers OK of a number field K but a polynomial ring Z[x]/f for a monic irreducible f in Z[x]. We show that there exist reductions between all of these six problems that incur limited parameter losses. More precisely: we prove that the (decision/search) dual to primal reduction from Lyubashevsky et al. [EUROCRYPT 2010] and Peikert [SCN 2016] can be implemented with a small error rate growth for all rings (the resulting reduction is nonuniform polynomial time); we extend it to polynomial-time reductions between (decision/search) primal RLWE and PLWE that work for a family of polynomials f that is exponentially large as a function of deg f (the resulting reduction is also non-uniform polynomial time); and we exploit the recent technique from Peikert et al. [STOC 2017] to obtain a search to decision reduction for RLWE. The reductions incur error rate increases that depend on intrinsic quantities related to K and f.
Based on joint work with Miruna Roșca and Damien Stehlé.
- 16h00, Cécile Pierrot, LORIA : Discrete Logarithm Lattices
