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. S'il n'existe pas à l'heure actuelle de calculateur quantique représentant une menace concrète sur la sécurité des cryptosystèmes déployés, ces algorithmes permettent conceptuellement de résoudre certains problèmes calculatoires sur lesquels sont fondés plusieurs primitives populaires. Algorithme de Shor En 1995, Peter Shor a publié un algorithme permettant de résoudre le problème du logarithme discret et le problème de la factorisation des entiers. Cet algorithme, utilisant les spécificités d'un calculateur quantique (dont on n'avait alors pas encore construit de prototypes), produit une réponse en temps polynomial. En comparaison, les meilleurs algorithmes classiques connus pour ces problèmes ont une complexité exponentielle en général, et sous-exponentielle mais sur-polynomiale pour les corps finis. En résumé, pour ces deux problèmes, aucun algorithme classique efficace n'est connu, mais puisqu'un algorithme quantique efficace est disponible, on dit qu'ils appartiennent à la classe de complexité BQP. En conséquence, les constructions cryptographiques dont la sécurité repose sur le problème du logarithme discret (notamment l'échange de clé de Diffie-Hellman et la signature ECDSA), ou sur le problème de la factorisation d'entiers (notamment la signature RSA) seraient vulnérables à un attaquant disposant d'un calculateur quantique suffisamment grand et fiable. L'algorithme de Grover, quant à lui, améliore de manière faible mais générique l'efficacité des problèmes de recherche.

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

Catégories associées (4)

Concepts associés (5)

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.

Problème de réseau

In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: Lattice problems are an example of NP-hard problems which have been shown to be average-case hard, providing a test case for the security of cryptographic algorithms. In addition, some lattice problems which are worst-case hard can be used as a basis for extremely secure cryptographic schemes.

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

Sécurité des systèmes d'information

alt=Data center du provider CyberBunker |vignette|Centre de données du fournisseur d'accès . La sécurité des systèmes d’information (SSI) ou plus simplement sécurité informatique, est l’ensemble des moyens techniques, organisationnels, juridiques et humains nécessaires à la mise en place de moyens visant à empêcher l'utilisation non autorisée, le mauvais usage, la modification ou le détournement du système d'information. Assurer la sécurité du système d'information est une activité du management du système d'information.

Génie informatique

Le génie informatique, ou l'ingénierie informatique, est une discipline qui traite de la conception, du développement et de la fabrication de systèmes informatiques, aussi bien d'un point de vue matériels que logiciels. Le terme anglais computer engineering est parfois utilisé dans un sens plus restreint, considérant le génie informatique comme une discipline reliée au génie électrique, et fait alors référence à la conception, au développement et à la fabrication du matériel uniquement.

Applied sciences

The following outline is provided as an overview of and topical guide to applied science: Applied science – the branch of science that applies existing scientific knowledge to develop more practical applications, including inventions and other technological advancements. Science itself is the systematic enterprise that builds and organizes knowledge in the form of testable explanations and predictions about the universe. Applied cryptography – applications of cryptography.