Learning With Errors (LWE) and Public Key Encryption || @ CMU || Lecture 25d of CS Theory Toolkit

Item: Learning With Errors (LWE) and Public Key Encryption || @ CMU || Lecture 25d of CS Theory Toolkit
Rating: 5
Author: PostSingularity Institute

par Ryan O'Donnell

Sciences formelles & physiques Sciences — Généralités & Histoire GPInformation et traitement de données : généralités GPJProgrammation et cryptologie

🎙 Ryan O'Donnell 👥 14K 📅 13 juillet 2020 ⏱ 25 min 👁 5K 📄 cours magistral 🧭 2026-08-17

Disponible en : Français (actuel) English

Mots-clés

LWEcryptographie à clé publiquelatticestrapdoor permutationspost-quantique

Résumé

Ce cours de la série ‘CS Theory Toolkit’ de l’université Carnegie Mellon, donné par Ryan O’Donnell, présente le problème Learning With Errors (LWE) et son rôle central dans la construction de schémas de chiffrement à clé publique. Le professeur commence par rappeler les bases du chiffrement à clé publique, en soulignant la différence avec le chiffrement symétrique. Il aborde ensuite la menace que représentent les ordinateurs quantiques pour les systèmes classiques comme RSA, via l’algorithme de Shor, et introduit la cryptographie post-quantique. Le cœur de la vidéo est l’explication du problème LWE : sa définition formelle, ses paramètres, et l’intuition de sa difficulté. O’Donnell détaille le théorème de Regev (2005) qui établit une réduction du pire cas au cas moyen pour certains problèmes de réseaux euclidiens (lattices), ce qui a valu à Regev le prix Gödel. Il présente ensuite concrètement un schéma de chiffrement à clé publique à un bit basé sur LWE, en expliquant la génération des clés, le chiffrement et le déchiffrement, ainsi que la preuve de correction. Enfin, il discute des avantages de la cryptographie fondée sur les lattices : résistance aux attaques quantiques, possibilité de construire des primitives avancées comme le chiffrement totalement homomorphe, et efficacité comparable aux méthodes classiques. La vidéo se conclut par une invitation à poser des questions.

215 mots

Évaluation critique

Valeur des informations & solidité de l’argumentation

La valeur des informations est très élevée : le cours fournit une explication claire et rigoureuse d’un sujet avancé de cryptographie, en s’appuyant sur des définitions formelles et des théorèmes. L’argumentation est solide : le professeur justifie chaque étape, explique les intuitions derrière les constructions, et mentionne les preuves (même si elles ne sont pas détaillées). Il prend soin de distinguer les hypothèses de difficulté et les réductions, et souligne les limites des approches classiques. La présentation est pédagogique et progressive, ce qui renforce la crédibilité du contenu.

Rigueur scientifique, qualité des sources, adéquation du titre

La rigueur scientifique est exemplaire : le cours est dispensé par un expert reconnu, les définitions sont précises, et les résultats sont attribués correctement (Regev, Peikert, etc.). Les sources mentionnées sont pertinentes : le manuel ‘A course in cryptography’ de Pass et Shelat est cité comme ressource, et les liens vers la page du professeur et le cours Diderot sont fournis. L’adéquation entre le titre et le contenu est parfaite : le titre annonce exactement le sujet traité. Aucune publicité n’est présente dans la vidéo.

188 mots

Adéquation titre / contenu

Le titre décrit exactement le contenu : la présentation du problème LWE et son utilisation pour la cryptographie à clé publique.

Qualité & fiabilité

9/10

Cours universitaire de niveau master/doctorat dispensé par un professeur de Carnegie Mellon, spécialiste reconnu en informatique théorique. Le contenu est rigoureux, les définitions sont précises et les preuves sont esquissées avec soin. La vidéo s'appuie sur des résultats publiés (Regev 2005) et des références académiques.

Moments clés

Repères établis par PSI à partir de la transcription : le créateur n'a pas défini de chapitres.

Sources citées

Page personnelle de Ryan O'Donnell — Page du professeur, mentionnée comme ressource pour le cours.
Cours CS Theory Toolkit sur Diderot — Page du cours complet, mentionnée comme ressource.
Photographie de Rebecca Kiger — Crédit photo de la miniature, mentionné dans la description.

Sources concordantes

On lattices, learning with errors, random linear codes, and cryptography — Article fondateur de Regev (2005) qui introduit LWE et la réduction pire cas / cas moyen.
A course in cryptography — Manuel de Pass et Shelat, cité comme ressource dans la description.

Apport & nouveautés

Cette vidéo apporte une explication claire et accessible d’un sujet de pointe en cryptographie, le problème LWE, qui est au cœur de nombreuses constructions modernes. Elle met en lumière l’importance des réductions pire cas / cas moyen et la robustesse de la cryptographie basée sur les réseaux face aux ordinateurs quantiques. Le cours est particulièrement utile pour les étudiants et chercheurs souhaitant comprendre les fondements théoriques de la cryptographie post-quantique.

Pour aller plus loin :

Learning with errors (article Wikipédia) — Article de synthèse sur le problème LWE, ses variantes et applications.
Lattice-based cryptography (article Wikipédia) — Vue d’ensemble de la cryptographie fondée sur les réseaux.
Oded Regev (page personnelle) — Page du chercheur ayant introduit LWE, avec ses publications.
Shor’s algorithm (article Wikipédia) — Algorithme quantique qui menace RSA, contexte de la cryptographie post-quantique.
Fully homomorphic encryption (article Wikipédia) — Primitive avancée construite à partir de LWE.

148 mots

Profil radar

Le profil radar est très équilibré, avec des scores élevés dans toutes les dimensions. La quantité d'information est importante, la qualité est excellente, le niveau technique est avancé, et la fiabilité est maximale. Cela reflète un contenu dense, rigoureux et parfaitement adapté à un public spécialisé.

Fiabilité 9/10