Classical hardness of learning with errors

Brakerski, Zvika; Roux-Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien

doi:10.1145/2488608.2488680

preprintMay 28, 2013Closed access

Classical hardness of learning with errors

ZBZvika Brakerski ARAdeline Roux-Langlois CPChris Peikert OROded Regev DSDamien Stehlé

Stanford University · École Normale Supérieure de Lyon · +3 more institutions

Indexed incrossref

Abstract

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems. Previously this was only known under quantum reductions.

Citation impact

596

total citations

FWCI: 82.52
Percentile: 100%
References: 53

Citations per year

Authors

ZB
Zvika BrakerskiCorresponding
Stanford University
AR
Adeline Roux-Langlois
École Normale Supérieure de Lyon
CP
Chris Peikert
Georgia Institute of Technology
OR
Oded Regev
New York University, Courant Institute of Mathematical Sciences
DS
Damien Stehlé
École Normale Supérieure de Lyon

Topics & keywords

Topics

Cryptography and Data Security100%
Machine Learning and Algorithms100%
Stochastic Gradient Optimization Techniques99%

Keywords

Learning with errors
Computer science
Quantum
Lattice (music)
Artificial intelligence
Algorithm
Theoretical computer science
Cryptography

No related works found for this paper.