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-quantiqueModèle:SfnModèle:,Modèle:Sfn. 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 2018Modèle:Sfn.

Principe

Si $s$ est un vecteur secret, alors il est aisé de retrouver $s$ é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 $s$ à partir de nombreuses entrées $\{(𝐚,⟨𝐚,𝐬⟩+e)\}$, lorsque le bruit $e$ est tiré de distributions appropriées.

Énoncé

On considère la distribution gaussienne discrète suivante, donnée pour chaque entier $x$ parModèle:Sfn :$$D_{\mathbb{Z},\sigma ,c}(x)=\frac{\exp (-\pi (x-c{)}^2/{\sigma }^2)}{\sum _{k\in \mathbb{Z}}\exp (-\pi (k-c{)}^2/{\sigma }^2)}$$Cette distribution peut être échantillonnée en temps quasi linéaireModèle:Sfn et permet de construire l'objet suivant : soient les entiers $n\ge 1$, $q\ge 2$, un paramètre réel $\alpha \in [0,1]$, et un vecteur $𝐬\in {\mathbb{Z}}_q^n$, alors la distribution LWE $D_{n,q,\alpha }(𝐬)$ définie sur ${\mathbb{Z}}_q^n\times {\mathbb{Z}}_q$ de la manière suivante :

• On échantillonne le « terme d'erreur » $e\leftarrow D_{\mathbb{Z},\alpha \cdot q,0}$
• On échantillonne uniformément $𝐚\leftarrow U({\mathbb{Z}}_q^n)$
• On retourne le couple $(𝐚,⟨𝐚,𝐬⟩+emodq)$

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 $D_{n,q,\alpha }(𝐬)$, retrouver $𝐬$.
• Le problème de décision LWE : si $𝐬\in {\mathbb{Z}}_q^n$ est tiré uniformément au hasard, distinguer la distribution $D_{n,q,\alpha }(𝐬)$ de la distribution uniforme sur ${\mathbb{Z}}_q^n\times {\mathbb{Z}}_q$.

Le paramètre $\alpha$ module la difficulté du problème : si $\alpha =0$, 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 $\alpha =1$, 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é difficileModèle:Sfn, cela rend attrayant l'utilisation de LWE comme base sur laquelle construire des primitives cryptographiques.

Résultats de complexité

Les travaux d'Oded RegevModèle:Sfn et de Brakerski et al.Modèle:Sfn montrent que la résolution du problème d'apprentissage avec erreurs est au moins aussi difficile que de trouver approximativement le Modèle:Lien d'un réseau euclidien, un problème supposé difficile pour lequel aucun algorithme efficace n'est connu lorsque la dimension du réseau augmente. Plus spécifiquement, si $\alpha >0$ et $q$ premier satisfont $\alpha q>2\sqrt{n}$, avec $q\le \mathrm{poly}(n)$ alors il existe une réduction quantique polynomiale du problème ${\mathrm{GapSVP}}_{\gamma }^{(n)}$ au problème de décision sur $D_{n,q,\alpha }$ avec $\gamma =\tilde{O}(n/\alpha )$Modèle:Sfn. Il existe également une réduction classique polynomiale à ${\mathrm{GapSVP}}_{\gamma }^{(\sqrt{n})}$Modèle:SfnModèle:,Modèle:Sfn.

Le problème du plus court vecteur est connu pour être NP-difficile (via réduction aléatoire) lorsque l'on souhaite le résoudre de façon exacteModèle:SfnModèle:,Modèle:Sfn, ou avec un tout petit facteur d'approximationModèle:Sfn. Malheureusement, ces cas ne couvrent pas les facteurs d'approximations polynomiaux, obtenus lors de la réduction du problème du plus court vecteur au problème LWE. Ainsi, il n'existe pour l'instant pas de réduction prouvant que le problème LWE est NP-difficile.

Il est conjecturé que même un ordinateur quantique ne permettrait pas de résoudre efficacement le problème LWE.

Variantes structurées

Il existe des variantes structurées du problème LWE, c'est-à-dire des variantes où l'on se restreint à des réseaux ayant pour base une matrice structurée (comme par exemple une matrice circulante). Parmi ces variantes structurées, les plus connues sont Polynomial-LWEModèle:Sfn, Ring-LWEModèle:Sfn ou encore Module-LWEModèle:Sfn.

Utilisation en cryptographie

Les résultats de complexité sont encourageants pour le développement de cryptosystèmes post-quantiques. Ainsi, des protocoles d'échange de cléModèle:SfnModèle:,Modèle:SfnModèle:,Modèle:Sfn, de signatureModèle:Sfn, de chiffrementModèle:SfnModèle:,Modèle:Sfn, de chiffrement homomorpheModèle:SfnModèle:,Modèle:Sfn, ainsi que des fonctions de hachageModèle:Sfn 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 algorithmesModèle:Sfn dans son navigateur Google Chrome pour certains servicesModèle:Sfn.

En pratique, l'anneau choisi est généralement un quotient de la forme $\mathbb{Z}[X]/({\mathrm{\Phi }}_m(X))$ avec ${\mathrm{\Phi }}_m(X)$ le $m$-ième polynôme cyclotomique. On parle alors de ring-LWE. Le bruit est ici encore échantillonné à partir d'une distribution gaussienne discrèteModèle:Sfn. 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 accrueModèle:Sfn.

Notes et références

Notes

• Modèle:Lien web.
• Modèle:Lien web.
• Modèle:Lien web.

Bibliographie

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.

Articles connexes

• Informatique quantique
• Cryptographie post-quantique
• Hypothèse calculatoire