TY - GEN

T1 - Classical hardness of learning with errors

AU - Brakerski, Zvika

AU - Langlois, Adeline

AU - Peikert, Chris

AU - Regev, Oded

AU - Stehlé, Damien

PY - 2013

Y1 - 2013

N2 - We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent crypto- graphic constructions, most notably fully homomorphic encryption schemes.

AB - We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent crypto- graphic constructions, most notably fully homomorphic encryption schemes.

KW - Lattices

KW - Learning with errors

UR - http://www.scopus.com/inward/record.url?scp=84879829096&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879829096&partnerID=8YFLogxK

U2 - 10.1145/2488608.2488680

DO - 10.1145/2488608.2488680

M3 - Conference contribution

AN - SCOPUS:84879829096

SN - 9781450320290

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 575

EP - 584

BT - STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing

T2 - 45th Annual ACM Symposium on Theory of Computing, STOC 2013

Y2 - 1 June 2013 through 4 June 2013

ER -