2026-07-20T07:46:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1892 2024-03-06T11:08:27Z ddc:004 open_access

Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem Peikert, Chris Lattice-based cryptography learning with errors quantum computation We construct public-key cryptosystems that are secure assuming the *worst-case* hardness of approximating the shortest vector problem on lattices. Prior cryptosystems with worst-case connections (e.g., the Ajtai-Dwork system) were based either on a *special case* of the shortest vector problem, or on the conjectured hardness of lattice problems for *quantum* algorithms. Our main technical innovation is a reduction from certain variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. In addition, we construct new cryptosystems based on LWE, including a very natural chosen ciphertext-secure system that has a much simpler description and tighter underlying worst-case approximation factor than prior constructions. (Duration: 30 minutes, on or before Wednesday.) Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chris Peikert 2009 Is Part Of Dagstuhl Seminar Proceedings, Volume 8491, Theoretical Foundations of Practical Information Security (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.08491.4 urn:nbn:de:0030-drops-18922 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08491.4 eng https://creativecommons.org/licenses/by/4.0/legalcode