2013 · 597 citations · 18 references
ComputingComputer ScienceMathematicsAlgorithmsCryptographyTheory Of ComputationCryptographic ComplexityHomomorphic EncryptionLattice-based CryptographyQuantum Complexity TheoryQuantum ComputationQuantum CryptographyCryptographic ReductionsFully Homomorphic EncryptionHardnessLearning With ErrorsLearning With Errors ProblemProblem HardnessReductionsWorst-case Complexity
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.
18
Fully homomorphic encryption using ideal lattices
Craig Gentry · 2009 · 6.6K citations
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · Journal of the ACM · 2009 · 2.2K citations
A Pseudorandom Generator from any One-way Function
Johan Håstad, Russell Impagliazzo, Leonid A. Levin et al. · SIAM Journal on Computing · 1999 · 1.7K citations
Efficient Fully Homomorphic Encryption from (Standard) LWE
Zvika Brakerski, Vinod Vaikuntanathan · 2011 · 1.5K citations