Ê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 Graph Search.
Concept
Lattice-based cryptography
Résumé
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. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.
In 1996, Miklós Ajtai introduced the first lattice-based cryptographic construction whose security could be based on the hardness of well-studied lattice problems, and Cynthia Dwork showed that a certain average-case lattice problem, known as Short Integer Solutions (SIS), is at least as hard to solve as a worst-case lattice problem. She then showed a cryptographic hash function whose security is equivalent to the computational hardness of SIS.
In 1998, Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman introduced a lattice-based public-key encryption scheme, known as NTRU. However, their scheme is not known to be at least as hard as solving a worst-case lattice problem.
The first lattice-based public-key encryption scheme whose security was proven under worst-case hardness assumptions was introduced by Oded Regev in 2005, together with the Learning with Errors problem (LWE). Since then, much follow-up work has focused on improving Regev's security proof and improving the efficiency of the original scheme. Much more work has been devoted to constructing additional cryptographic primitives based on LWE and related problems. For example, in 2009, Craig Gentry introduced the first fully homomorphic encryption scheme, which was based on a lattice problem.
Source officielle
À 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.