Apprentissage avec erreurs

Si ${\displaystyle s}$ est un vecteur secret, alors il est aisé de retrouver ${\displaystyle s}$ étant donné des produits scalaires ${\displaystyle \langle \mathbf {a} ,\mathbf {s} \rangle }$ si l'on connaît suffisamment de vecteurs ${\displaystyle \mathbf {a} }$ : 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 ${\displaystyle s}$ à partir de nombreuses entrées ${\displaystyle \{(\mathbf {a} ,\langle \mathbf {a} ,\mathbf {s} \rangle +e)\}}$, lorsque le bruit ${\displaystyle e}$ est tiré de distributions appropriées.

On considère la distribution gaussienne discrète suivante, donnée pour chaque entier ${\displaystyle x}$ par[4] :

$${\displaystyle 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éaire[5] et permet de construire l'objet suivant : soient les entiers ${\displaystyle n\geq 1}$, ${\displaystyle q\geq 2}$, un paramètre réel ${\displaystyle \alpha \in [0,1]}$, et un vecteur ${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$, alors la distribution LWE ${\displaystyle D_{n,q,\alpha }(\mathbf {s} )}$ définie sur ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {Z} _{q}}$ de la manière suivante :

• On échantillonne le « terme d'erreur » ${\displaystyle e\gets D_{\mathbb {Z} ,\alpha \cdot q,0}}$
• On échantillonne uniformément ${\displaystyle \mathbf {a} \gets U(\mathbb {Z} _{q}^{n})}$
• On retourne le couple ${\displaystyle \left(\mathbf {a} ,\left\langle \mathbf {a} ,\mathbf {s} \right\rangle +e{\bmod {q}}\right)}$

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

Le paramètre ${\displaystyle \alpha }$ module la difficulté du problème : si ${\displaystyle \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 ${\displaystyle \alpha =1}$, le bruit remplace toute l'information sur ${\displaystyle \mathbf {s} }$ 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.

Les travaux d'Oded Regev[7] et de Brakerski et al.[8] montrent que la résolution du problème d'apprentissage avec erreurs est au moins aussi difficile que de trouver approximativement le plus court vecteur (en) 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 ${\displaystyle \alpha >0}$ et ${\displaystyle q}$ premier satisfont ${\displaystyle \alpha q>2{\sqrt {n}}}$, avec ${\displaystyle q\leq \operatorname {poly} (n)}$ alors il existe une réduction quantique polynomiale du problème ${\displaystyle \operatorname {GapSVP} _{\gamma }^{(n)}}$ au problème de décision sur ${\displaystyle D_{n,q,\alpha }}$ avec ${\displaystyle \gamma ={\widetilde {O}}(n/\alpha )}$[7]. Il existe également une réduction classique polynomiale à ${\displaystyle \operatorname {GapSVP} _{\gamma }^{({\sqrt {n}})}}$[9] - [8].

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 exacte[6] - [10], ou avec un tout petit facteur d'approximation[11]. 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.

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-LWE[12], Ring-LWE[13] ou encore Module-LWE[14].

Les résultats de complexité sont encourageants pour le développement de cryptosystèmes post-quantiques. Ainsi, des protocoles d'échange de clé[15] - [16] - [17], de signature[18], de chiffrement[7] - [9], de chiffrement homomorphe[19] - [20], ainsi que des fonctions de hachage[21] 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[17] dans son navigateur Google Chrome pour certains services[22].

En pratique, l'anneau choisi est généralement un quotient de la forme ${\displaystyle \mathbb {Z} [X]/(\Phi _{m}(X))}$ avec ${\displaystyle \Phi _{m}(X)}$ le ${\displaystyle m}$-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[16].

• [Ajtai 1996] (en) Miklós Ajtai, « Generating Hard Instances of Lattice Problems », STOC,‎ 1996, p. 99−108
• [Ajtai 1998] (en) Miklós Ajtai, « The shortest vector problem in L₂ is NP-hard for randomized reductions », STOC,‎ 1998, p. 10–19
• [Alkim et al. 2016] (en) Erdem Alkim, Léo Ducas, Thomas Pöppelmann et Peter Schwabe, « Post-quantum Key Exchange - A New Hope. », USENIX Security Symposium,‎ 2016, p. 327-343
• [Bos et al. 2015] (en) J. W. Bos, C. Costello, M. Naehrig et D. Stebila, « Post-Quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem », S&P,‎ mai 2015, p. 553–570 (DOI 10.1109/sp.2015.40, lire en ligne, consulté le 28 février 2018)
• [Brakerski et al. 2013] (en) Zvika Brakerski, Adeline Langlois, Chris Peikert et Oded Regev, « Classical hardness of learning with errors », Symposium on Theory of Computing Conference, STOC'13, ACM,‎ 1^er juin 2013, p. 575–584 (ISBN 9781450320290, DOI 10.1145/2488608.2488680, lire en ligne, consulté le 23 mars 2018)
• [Brakerski et Vaikuntanathan 2011] (en) Zvika Brakerski et Vinod Vaikuntanathan, « Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages », Crypto, Springer, Berlin, Heidelberg, lNCS,‎ 14 août 2011, p. 505–524 (ISBN 9783642227912, DOI 10.1007/978-3-642-22792-9_29, lire en ligne, consulté le 28 février 2018)
• [Ducas et al. 2013] (en) Léo Ducas, Alain Durmus, Tancrède Lepoint et Vadim Lyubashevsky, « Lattice Signatures and Bimodal Gaussians », Crypto, Berlin, Heidelberg, Springer, lecture Notes in Computer Science,‎ 2013, p. 40–56 (ISBN 9783642400407 et 9783642400414, DOI 10.1007/978-3-642-40041-4_3, lire en ligne, consulté le 23 mars 2018)
• [Dwarakanath et Galbraith 2014] (en) Nagarjun C. Dwarakanath et Steven D. Galbraith, « Sampling from discrete Gaussians for lattice-based cryptography on a constrained device », Applicable Algebra in Engineering, Communication and Computing, vol. 25, n^o 3,‎ 1^er juin 2014, p. 159–180 (ISSN 0938-1279 et 1432-0622, DOI 10.1007/s00200-014-0218-3, lire en ligne, consulté le 28 février 2018)
• [Gentry, Sahai et Waters 2013] (en) Craig Gentry, Amit Sahai et Brent Waters, « Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based », Crypto, Springer, lNCS,‎ 2013 (DOI 10.1007/978-3-642-40041-4_5)
• [Langlois et Stehlé 2015] (en) Adeline Langlois et Damien Stehlé, « Worst-case to average-case reductions for module lattices », Designs, Codes and Cryptography, vol. 75, n^o 3,‎ juin 2015, p. 565--599 (ISSN 0925-1022, DOI 10.1007/s10623-014-9938-4, lire en ligne, consulté le 20 avril 2020)
• [Lyubashevsky 2012] (en) Vadim Lyubashevsky, « Lattice Signatures without Trapdoors », Eurocrypt, Springer, Berlin, Heidelberg, lNCS,‎ 15 avril 2012, p. 738–755 (ISBN 9783642290107, DOI 10.1007/978-3-642-29011-4_43, lire en ligne, consulté le 28 février 2018)
• [Lyubashevsky et al. 2008] (en) Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert et Alon Rosen, « SWIFFT: A Modest Proposal for FFT Hashing », FSE, Springer, Berlin, Heidelberg, lNCS,‎ 10 février 2008, p. 54–72 (ISBN 9783540710387, DOI 10.1007/978-3-540-71039-4_4, lire en ligne, consulté le 28 février 2018)
• [Lyubashevsky, Peikert et Regev 2013] (en) Vadim Lyubashevsky, Chris Peikert et Oded Regev, « On Ideal Lattices and Learning with Errors over Rings », Journal of the ACM (JACM), vol. 60, n^o 6,‎ 1^er novembre 2013, p. 43 (ISSN 0004-5411, DOI 10.1145/2535925, lire en ligne, consulté le 28 février 2018)
• [Micciancio 1998] (en) D. Micciancio, « The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant », FOCS,‎ 1998 (ISBN 0-8186-9172-7, lire en ligne, consulté le 16 mars 2018)
• [Micciancio 2011] (en) Daniele Micciancio, Encyclopedia of Cryptography and Security, Springer, Boston, MA, 2011 (DOI 10.1007/978-1-4419-5906-5_417, lire en ligne), p. 713–715
• [Peikert 2009] (en) Chris Peikert, « Public-key cryptosystems from the worst-case shortest vector problem », STOCS, ACM,‎ 31 mai 2009, p. 333–342 (ISBN 9781605585062, DOI 10.1145/1536414.1536461, lire en ligne, consulté le 28 février 2018)
• [Peikert 2014] (en) Chris Peikert, « Lattice Cryptography for the Internet », PQCrypto, Springer, Cham, lNCS,‎ 1^er octobre 2014, p. 197–219 (ISBN 9783319116587, DOI 10.1007/978-3-319-11659-4_12, lire en ligne, consulté le 28 février 2018)
• [Regev 2005] (en) Oded Regev, « On lattices, learning with errors, random linear codes, and cryptography », STOCS,‎ 2005 (ISBN 1-58113-960-8, DOI 10.1145/1060590.1060603, lire en ligne, consulté le 16 mars 2018)
• [Stehlé et al. 2009] (en) Damien Stehlé, Ron Steinfeld, Keisuke Tanaka et Keita Xagawa, « Efficient Public Key Encryption Based on Ideal Lattices », Asiacrypt,‎ 2009, p. 617−635

• Cryptographie post-quantique
• Hypothèse calculatoire