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[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
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é
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é
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 et premier satisfont , avec alors il existe une réduction quantique polynomiale du problème au problème de décision sur avec [7]. Il existe également une réduction classique polynomiale à [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.
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-LWE[12], Ring-LWE[13] ou encore Module-LWE[14].
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é[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 avec le -ième polynôme cyclotomique. On parle alors de ring-LWE. Le bruit est ici encore échantillonné à partir d'une distribution gaussienne 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].
Notes et références
Références
- ↑ Micciancio 2011.
- ↑ Compétition du NIST pour les standards de cryptographie post-quantique.
- ↑ Remise du prix Gödel à Oded Regev.
- ↑ a et b Dwarakanath et Galbraith 2014.
- ↑ Ducas et al. 2013.
- ↑ a et b Ajtai 1996.
- ↑ a b et c Regev 2005.
- ↑ a et b Brakerski et al. 2013.
- ↑ a et b Peikert 2009.
- ↑ Ajtai 1998.
- ↑ Micciancio 1998.
- ↑ Stehlé et al. 2009.
- ↑ Lyubashevsky, Peikert et Regev 2013.
- ↑ Langlois et Stehlé 2015.
- ↑ Peikert 2014.
- ↑ a et b Bos et al. 2015.
- ↑ a et b Alkim et al. 2016.
- ↑ Lyubashevsky 2012.
- ↑ Brakerski et Vaikuntanathan 2011.
- ↑ Gentry, Sahai et Waters 2013.
- ↑ Lyubashevsky et al. 2008.
- ↑ Expérience de Google sur les échanges de clefs Post-Quantique.
Notes
- « 2018 Gödel prize », sur EATCS.
- (en) National Institute of Standards and Technology, « Compétition du NIST pour les standards post-quantiques », (consulté le ).
- (en) Matt Braithwaite, « Experimenting with Post-Quantum Cryptography », sur security.googleblog.com, .
Bibliographie
- [Ajtai 1996] (en) Miklós Ajtai, « Generating Hard Instances of Lattice Problems », STOC, , p. 99−108.
- [Ajtai 1998] (en) Miklós Ajtai, « The shortest vector problem in L2 is NP-hard for randomized reductions », STOC, , 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, , 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 ).
- [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 ).
- [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, , p. 505–524 (ISBN 9783642227912, DOI 10.1007/978-3-642-22792-9_29, lire en ligne, consulté le ).
- [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, , p. 40–56 (ISBN 9783642400407 et 9783642400414, DOI 10.1007/978-3-642-40041-4_3, lire en ligne, consulté le ).
- [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 ).
- [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, (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, no 3, , p. 565--599 (ISSN 0925-1022, DOI 10.1007/s10623-014-9938-4, lire en ligne, consulté le ).
- [Lyubashevsky 2012] (en) Vadim Lyubashevsky, « Lattice Signatures without Trapdoors », Eurocrypt, Springer, Berlin, Heidelberg, lNCS, , p. 738–755 (ISBN 9783642290107, DOI 10.1007/978-3-642-29011-4_43, lire en ligne, consulté le ).
- [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, , p. 54–72 (ISBN 9783540710387, DOI 10.1007/978-3-540-71039-4_4, lire en ligne, consulté le ).
- [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 ).
- [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 ).
- [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 ).
- [Peikert 2014] (en) Chris Peikert, « Lattice Cryptography for the Internet », PQCrypto, Springer, Cham, lNCS, , p. 197–219 (ISBN 9783319116587, DOI 10.1007/978-3-319-11659-4_12, lire en ligne, consulté le ).
- [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 ).
- [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 connexes
Portail de la cryptologie
Portail de l'informatique théorique