• Oded Regev (CNRS, ENS, Paris, and Tel Aviv University) – Learning with Errors over Rings

Based on joint work with Vadim Lyubashevsky and Chris Peikert.

RESUME :The « learning with errors » (LWE) problem is to distinguish randomlinear equations, which have been perturbed by a small amount ofnoise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications.

Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. After a short introduction to the area, we will discuss recent work on making LWE and its applications truly efficient by exploiting extra algebraic structure. Namely, we will define the ring-LWE problem, and prove that it too enjoys very strong hardness guarantees. We will mention some recent cryptographic applications in this line of work. Oded.Regev-21-01-2011 (format pdf)

  • Marine Minier (INSA Lyon) – Quelques propriétés intégrales de Rijndael, LANE et Groestl

RESUME : Derrière ces étranges noms se cachent tout d’abord un chiffrement par blocs ou plutôt plusieurs versions d’un même chiffrement « Rijndael » dont la version pour des blocs de 128 bits est devenue le dernier standard de chiffrement américain l’AES en 2001. Quant à LANE et Groestl, il s’agit de deux candidats de la phase 1 de l’appel du NIST à la compétition SHA3 afin de standardiser une nouvelle fonction de hachage.

Nous nous intéresserons, dans cet exposé, à une forme d’attaques particulière contre ces algorithmes appelée cryptanalyse intégrale. Cette attaque a été introduite en 1997 par Lars Knudsen contre le chiffrement SQUARE puis ensuite formalisée en 2002 par David Wagner et Lars Knudsen. Il s’agit ici de faire prendre à un mot particulier du bloc à chiffrer toutes les valeurs possibles, les autres mots étant constants, afin d’observer après un certain nombre de tours de chiffrement des sommes de mots à 0. Ce type de propriétés, au même titre que les propriétés différentielles ou linéaires, permet de construire des relations statistiques ayant de grandes chances de se produire entre les entrées et les sorties d’un chiffrement limité à un nombre particulier de tours. On peut alors distinguer les sorties d’un chiffrement d’une suite aléatoire. Marine.Minier-21-01-2011 (format pdf)

  • Tony Ezome (Université de Toulouse) – Les nombres premiers : recherche et intérêt

RESUME : Le théorème fondamental de l’arithmétique stipule que tout entier se décompose, de manière unique à l’ordre près des facteurs, en produit de nombres premiers. Mais en pratique la factorisation des grands entiers est un problème difficile. La preuve de primalité est à la base du processus de factorisation d’un entier. Et aujourd’hui, la cryptographie symétrique utilise les nombres premiers pour chiffrer les messages. On peut le voir dans la construction de grands entiers difficilement factorisables réalisée par les cryptosystèmes RSA. D’autre part, on se sert des nombres premiers en cryptographie asymétrique pour fixer un corps de base $F_p$, considérer des courbes elliptiques $E/F_p$ définies sur ce corps de base et profiter de la difficulté du problème du logarithme discret dans le groupe des points de $E$ pour produire des cryptosystèmes d’une grande robustesse. La conception de critères de primalité et des algorithmes qui en découlent a donc toute son importance.

Dans cet exposé nous reviendrons sur les tests de primalité Miller-Rabin (probabiliste et très efficace en pratique), AKS (déterministe utilisant les extensions cyclotomiques, mais lent nn pratique) et ECPP (probabiliste et très puissant, il fournit un certificat de primalité) avant de présenter un nouveau critère de primalité : le critère AKS elliptique. Il s’agit d’une amélioration du test AKS qui utilise les courbes elliptiques. Tony.Ezome-21-01-2011 (format pdf). Une version longue est disponible.

  • Thomas Fuhr (ANSSI)– Cryptanalyse de fonctions de hachage : RadioGatun et Hamsi-256

RESUME : Les fonctions de hachage cryptographiques constituent un domaine dans lequel de nombreux développements sont apparus ces dernières années, tant du point de vue de la conception que du point de vue des attaques. Les techniques liées à la cryptanalyse différentielle ont mis à mal les standards de hachage existants. Cela a conduit le NIST à organiser la compétition SHA-3, dont l’objectif est la définition d’une nouvelle norme en matière de hachage.

Dans cet exposé nous nous intéressons à la cryptanalyse des fonctions de hachage, et à son évolution au cours des dernières années. La compétition SHA-3 requiert une capacité à évaluer la sécurité d’un nombre conséquent de fonctions de hachage en l’espace de 3 ans. De nombreux travaux récents mettent donc en lumière des vulnérabilités pas toujours directement exploitables de fonctions de hachage. De nouvelles techniques de cryptanalyse sont également apparues. Nous évoquerons particulièrement deux attaques contre des fonctions de hachage dont la fonction de compression est de bas degré algebrique. La première est une attaque en recherche de collisions sur RadioGatun, dont une partie des principes de conceptions ont conduit à la définition du candidat SHA-3 Keccak. Nous décrirons également une attaque en recherche de secondes préimages sur la fonction Hamsi-256, basée sur l’étude de ses propriétés algébriques. Thomas.Furr-21-01-2011 (format pdf)