Claire Delaplace, nouvelle membre de l'équipe GOC, fera un séminaire présentant ses travaux, le jeudi 24 septembre à 14h salle 401 EPI 2, à l’ensemble des membres du laboratoire.
Résumé:
Le problème Learning With Errors (LWE) est un problème majeur de la cryptographie à base de
réseaux euclidiens. Il consiste plus à moins à résoudre un système linéaire bruité As + e = b
modulo un entier q. Pour des paramètres bien choisis, il est connu pour être aussi difficile
à résoudre que des problèmes difficiles de réseaux euclidiens.
Nous nous intéressons ici à une variante sans réduction modulaire. Nous appelons ce problème
Integer-LWE (ILWE). C'est sans surprise que nous le trouvons beaucoup plus facile à résoudre
que LWE. Sous certaines conditions sur la distribution des coefficients de la matrice A et de
l'erreur e, nous montrons que ILWE peut se résoudre très facilement en utilisant la méthode des
moindres carrés. De plus, si le secret s est particulièrement creux, il est aussi possible de
résoudre le système en utilisant des méthodes d'acquisition comprimée.
Nous proposons également des bornes théoriques sur le nombre minimal de lignes que doit contenir
la matrice A pour retrouver s. Tout ceci nous permet d'améliorer une attaque, due à Espitau et
ses co-auteurs, contre le schéma de signature BLISS.
