Ouvrir le menu principal

Apprentissage avec erreurs

Problème algorithmique reposant sur les réseaux euclidiens dont la difficulté supposée résisterait à un ordinateur quantique.

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].

Sommaire

PrincipeModifier

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

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

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 cryptographieModifier

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érencesModifier

BibliographieModifier

  • [Ajtai 1996] (en) Miklós Ajtai, « Generating Hard Instances of Lattice Problems », STOC,‎ , p. 99−108
  • [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,‎ , 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,‎ , 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,‎ , 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, série LNCS,‎ , 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, série Lecture Notes in Computer Science,‎ , 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, no 3,‎ , 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, série LNCS,‎ (DOI 10.1007/978-3-642-40041-4_5)
  • [Lyubashevsky 2012] (en) Vadim Lyubashevsky, « Lattice Signatures without Trapdoors », Eurocrypt, Springer, Berlin, Heidelberg, série LNCS,‎ , 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, série LNCS,‎ , 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, no 6,‎ , 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,‎ (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, (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,‎ , 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, série LNCS,‎ , 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,‎ (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,‎ , p. 617−635

Articles connexesModifier