Apprentissage avec erreurs

L'apprentissage avec erreurs, souvent abrégé LWE (acronyme de l'anglais Learning With Errors), est un problème calculatoire supposé difficile. Il est au cœur de nombreux cryptosystèmes récents et constitue l'une des principales pistes de recherche pour le développement de la cryptographie post-quantique. L'introduction de ce problème par Oded Regev dans la communauté informatique, et ses travaux sur ce sujet, lui ont valu de recevoir le prix Gödel en 2018. Si est un vecteur secret, alors il est aisé de retrouver étant donné des produits scalaires si l'on connaît suffisamment de vecteurs : il s'agit d'un problème d'algèbre linéaire, qui se résout efficacement — par un pivot de Gauss par exemple. En revanche, si les produits scalaires ne sont connus qu'approximativement, alors le problème devient difficile sous certaines conditions. Plus précisément on ne connaît pas d'algorithmes efficaces pour retrouver le vecteur à partir de nombreuses entrées , lorsque le bruit est tiré de distributions appropriées. On considère la distribution gaussienne discrète suivante, donnée pour chaque entier par :Cette distribution peut être échantillonnée en temps quasi linéaire et permet de construire l'objet suivant : soient les entiers , , un paramètre réel , et un vecteur , alors la distribution LWE définie sur de la manière suivante : On échantillonne le « terme d'erreur » On échantillonne uniformément On retourne le couple Cette distribution permet de définir le problème « LWE » sous forme de problème de recherche ou de problème décisionnel: Le problème de recherche LWE : étant donnés des échantillons distribués selon , retrouver . Le problème de décision LWE : si est tiré uniformément au hasard, distinguer la distribution de la distribution uniforme sur . Le paramètre module la difficulté du problème : si , le bruit est absent, et le problème revient à la résolution d'un système linéaire, ce qui se résout en temps polynomial. En revanche, si , le bruit remplace toute l'information sur et rend impossible la résolution du problème.