Apprentissage avec erreurs | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

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. 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. 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. On considère la distribution gaussienne discrète suivante, donnée pour chaque entier par :Cette distribution peut être échantillonnée en temps quasi linéaire 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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (5)

Cours associés (3)

Séances de cours associées (14)

Apprentissage avec erreurs

Cryptographie post-quantique

La cryptographie post-quantique est une branche de la cryptographie visant à garantir la sécurité de l'information face à un attaquant disposant d'un calculateur quantique. Cette discipline est distincte de la cryptographie quantique, qui vise à construire des algorithmes cryptographiques utilisant des propriétés physiques, plutôt que mathématiques, pour garantir la sécurité. En l'effet, les algorithmes quantiques de Shor, de Grover et de Simon étendent les capacités par rapport à un attaquant ne disposant que d'un ordinateur classique.

Lattice-based cryptography

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers.

MATH-489: Number theory in cryptography

The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer s

CS-523: Advanced topics on privacy enhancing technologies

This advanced course will provide students with the knowledge to tackle the design of privacy-preserving ICT systems. Students will learn about existing technologies to prect privacy, and how to evalu

Ondes topologiques pour des applications de traitement de signaux robustes

Explore les ondes topologiques pour des applications robustes de traitement des signaux, en mettant l'accent sur la résistance aux perturbations et le paradigme de conception des systèmes topologiques.

Réseaux topologiques anomaux : théorie et expérience

Explore la robustesse anormale dans les réseaux topologiques non réciproques, couvrant les états topologiques de Floquet, les réseaux de diffusion unitaire et les implémentations pratiques.

Réseaux de dispersion topologique anomale

Explore la robustesse exceptionnelle du transport dans les réseaux de diffusion topologiques anomales, soulignant la supériorité du transport anomal sur le transport de Chern.