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.
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.
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.
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.
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.
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
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
Statistical learning theory for supervised learning and generalization in PAC and online models (VC theory, MDL/SRM, covering numbers, Radamacher Averages, boosting, compression, stability and connect
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.
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.
Couvre le développement historique et les concepts clés du cryptage homomorphe, en se concentrant sur le cryptosystème Paillier et le cryptosystème BGV.
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.
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.
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.
Since the advent of internet and mass communication, two public-key cryptographic algorithms have shared the monopoly of data encryption and authentication: Diffie-Hellman and RSA. However, in the last few years, progress made in quantum physics -- and mor ...
We provide faster algorithms and fine-grained reductions for lattice problems in general norms. ...
EPFL2023
,
A hash proof system (HPS) is a form of implicit proof of membership to a language. Out of the very few existing post-quantum HPS, most are based on languages of ciphertexts of code-based or lattice-based cryptosystems and inherently suffer from a gap cause ...