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 -