Apprentissage avec erreurs

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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[1],[2]. 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[3].

Principe[modifier | modifier le code]

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.

Énoncé[modifier | modifier le code]

On considère la distribution gaussienne discrète suivante, donnée pour chaque entier par[4] :

Cette distribution peut être échantillonnée en temps quasi-linéaire[5] 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.

Entre les deux, le problème de l'apprentissage avec erreurs s'interprète comme un problème de décodage dans un réseau euclidien, et dans certains cas il est démontré que les deux problèmes sont équivalents. Puisque le problème de décodage (ou du plus court vecteur) est réputé difficile[6], cela rend attrayant l'utilisation de LWE comme base sur laquelle construire des primitives cryptographiques.

Résultats de complexité[modifier | modifier le code]

Les travaux d'Oded Regev[7] et Chris Peikert[8] montrent que la résolution du problème d'apprentissage avec erreurs se ramène à trouver approximativement le plus court vecteur (en) d'un réseau euclidien, un problème difficile pour lequel aucun algorithme efficace n'est connu lorsque la dimension du réseau augmente.

Stehlé, Steinfeld, Tanaka et Xagawa ont montré en 2009 que le problème posté sur certains réseaux structurés (en particulier des réseaux d'idéaux) se réduisait quantiquement en moyenne à des problèmes de recherche de vecteurs courts sur des réseaux euclidiens dans lesquels le problème a été montré NP-difficile[9],[10],[11]. Plus spécifiquement, si et premier satisfont , avec alors il existe une réduction (quantique) polynomiale du problème au problème de décision sur avec . Il existe également une réduction classique polynomiale à [12],[7].

Sous l'hypothèse que P ≠ NP, il est conjecturé que même un ordinateur quantique ne suffirait pas à résoudre des instances aléatoires de ce problème efficacement.

Utilisation en cryptographie[modifier | modifier le code]

Les résultats de complexité sont encourageants pour le développement de cryptosystèmes post-quantiques. Ainsi, des protocoles d'échange de clé[13],[14],[15], de signature[16], de chiffrement[7],[8], de chiffrement homomorphe[17],[18], ainsi que des fonctions de hachage[19] ont été proposés, dont la sécurité s'appuie sur la difficulté à résoudre le problème d'apprentissage avec erreurs.

En 2016, Google a introduit de manière expérimentale l'un de ces algorithmes[15] dans son navigateur Google Chrome pour certains services[20].

En pratique, l'anneau choisi est généralement un quotient de la forme avec le -ième polynôme cyclotomique. On parle alors de ring-LWE. Le bruit est ici encore échantillonné à partir d'une distribution gausienne discrète[4]. Le problème de l'apprentissage avec erreur se ramène alors au calcul d'un vecteur court dans un réseau idéal. À l'heure actuelle il n'est pas prouvé qu'il s'agit encore, comme dans un réseau régulier, d'un problème difficile ; cependant aucune technique efficace n'est connue pour le résoudre. L'intérêt de ces choix est notamment de permettre une réduction substantielle de la taille des clés, et une efficacité algorithmique accrue[14].

Notes et références[modifier | modifier le code]

Références[modifier | modifier le code]

Notes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]