- Daniel Augot, LIX, INRIA Saclay – Décodage des codes de Reed-Solomon et logarithme discret dans les corps finis.
En commun avec François Morain.
Alors que le problème associé au décodage des Reed-Solomon est connu pour être NP-complet, on se fait pas bien quelles sont les instances difficiles, ni si les codes de Reed-Solomon standard font partie de ce ces instances.
Dans le but d’analyser les codes standard, Cheng et Wan étudient depuis 2004 comment le logarithme discret sur les corps non premiers se réduit à un certain problème de décodage des codes de Reed-Solomon. Leur objectif est de prouver la difficulté du décodage des codes de Reed-Solomon, en présence d’un grand nombre d’erreurs, sous l’hypothèse que le logarithme discret est difficile.
Nous nous sommes proposés d’étudier la réduction dans le sens inverse: utilisation d’algorithmes de décodage connus pour construire un algorithme de calcul de logarithmes discrets sur les corps finis. La méthode est une méthode de calcul d’index, où la découverte de relations repose sur le décodage (des codes de Reed-Solomon). Nous avons utilisé des algorithmes de décodage unique, comme celui de Gao, par opposition au décodage en liste. Ces méthodes ont été implantées en Magma et NTL. Bien que cette méthode ne semble pas aussi performante que les méthodes classiques à la Adleman, il y a toutefois de nombreuses thématiques originales qui émergent.
- Franck Landelle, DGA MI – Cryptanalysis of Full RIPEMD-128
Travail commun avec Thomas Peyrin
Nous proposons une nouvelle méthode de cryptanalyse pour les fonctions de hachage double-branche qui nous permet sur le standard RIPEMD-128 d’améliorer grandement les résultats connus. Précisement, nous sommes capable de construire un très bon chemin différentiel en plaçant un chemin avec une partie non linéaire dans chacune des branches de la fonction de compression de RIPEMD-128. Ces parties non linéaires ne sont pas nécessairement sur les toutes premières étapes. Pour gérer les parties non linéaires des chemins différentiels, nous proposons une nouvelle méthode pour l’utilisation des degrées de liberté se déroulant 2 deux phases principales : la vérification des parties non linéaires et le merge des chemins des 2 branches via l’état initial. Nous obtenons la première collision sur la fonction de compression complète de RIPEMD-128 ainsi qu’un distingueur sur cette fonction de hachage. Les étapes de l’attaque ont été programmées et les expériences confirment nos raisonnements et complexités de l’attaque. Nos résultats montrent que l’une des dernières primitives de hachage de conception comptemporaine de SHA-1 non cassée n’était pas aussi sûre que prévue.
- Gaël Thomas, Université de Limoges – Diffusion dans les schémas de Feistel généralisés
Avec les réseaux substitution-permutation, les schémas de Feistel consti- tuent l’une des deux grandes familles de chiffrement par bloc. Popularisé par le DES, le schéma de Feistel a depuis subi de nombreuses généralisations visant à augmenter le nombre de blocs en lesquels est subdivisé le message. Ceci amène alors à se poser la question du nombre minimum d’itérations à effectuer pour « bien mélanger » ces blocs. Plus précisément, on s’intéresse ici à la notion de (délai de) diffusion qui est le nombre minimum de tours au bout desquels chaque bloc en sortie dépend de tous les blocs en entrée. Dans cet exposé, on se propose d’abord de faire un tour d’horizon des différentes familles de schémas de Feistel généralisés existantes puis d’en ex- hiber une représentation matricielle unifiée en lien avec la notion de diffusion. Finalement cette représentation permettra de définir une nouvelle classe de tels schémas bien adaptés pour des applications cryptographique
- Adeline Langlois, LIP, ENS Lyon – Classical Hardness of Learning With Errors
This work has been done with Z. Brakerski, C. Peikert, O. Regev and D. Stehlé.
The decision Learning With Errors (LWE) problem, introduced by Regev in 2005 has proven an invaluable tool for designing provably secure cryptographic protocols. We show that LWE is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.
