salle A. Turing CE4
17 avril 2012 - 14h00
Le probleme du sac a dos modulaire est difficile en moyenne.
par Malika Izabachene de ENS Cachan
Résumé : Les primitives cryptographiques sont basées sur des problèmes difficiles en moyenne, au sens où presque toutes les instances sont difficiles. Traditionnellement, cette difficulté moyenne repose sur des expériences, ou sur la difficulté moyenne d'autres problèmes.
Pourtant, en 1996, Ajtai a montré que résoudre n'importe quel problème de réseaux difficile dans le pire cas se réduisait à approcher le problème du plus court vecteur dans un réseau, sur une classe particulière, celle des réseaux de type SIS. Ainsi, l'existence de la moindre instance difficile d'un problème de réduction de réseau entraîne la difficulté de presque toutes les instances du problème SIS.
Cette découverte constitue une brique fondamentale dans la construction des schémas à base de réseaux. Alors que les problèmes classiques tels que RSA et le log discret ne sont supposés difficiles que pour des instances particulières, avec cette réduction, il devient désormais possible de baser la cryptographie sur des problèmes difficiles dans le pire cas. Malheureusement, la contrainte d'utiliser des réseaux de type SIS induit des cryptosystèmes avec un volume et une dimension qui restent assez élevés et les schémas qui en dérivent restent peu exploitables en pratique.
Dans cet exposé, nous présentons une nouvelle réduction pire-cas vers cas moyen, qui prouve à la fois la difficulté de réduire des réseaux aléatoires, et la difficulté du problème du sac à dos. Cela conduit à des cryptosystèmes plus naturels, et même quatre fois plus petits que leurs prédécesseurs pour un même niveau de sécurité.
Travail joint avec Nicolas Gama.
