TY - GEN
T1 - Pseudorandomness of ring-LWE for any ring and modulus
AU - Peikert, Chris
AU - Regev, Oded
AU - Stephens-Davidowitz, Noah
N1 - Publisher Copyright:
© 2017 ACM.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.
PY - 2017/6/19
Y1 - 2017/6/19
N2 - We give a polynomial-time quantum reduction from worst-case (ideal) lattice problems directly to decision (Ring-)LWE. This extends to decision all the worst-case hardness results that were previously known for the search version, for the same or even better parameters and with no algebraic restrictions on the modulus or number field. Indeed, our reduction is the first that works for decision Ring-LWE with any number field and any modulus.
AB - We give a polynomial-time quantum reduction from worst-case (ideal) lattice problems directly to decision (Ring-)LWE. This extends to decision all the worst-case hardness results that were previously known for the search version, for the same or even better parameters and with no algebraic restrictions on the modulus or number field. Indeed, our reduction is the first that works for decision Ring-LWE with any number field and any modulus.
KW - Lattices
KW - Learning with errors
UR - http://www.scopus.com/inward/record.url?scp=85024384539&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85024384539&partnerID=8YFLogxK
U2 - 10.1145/3055399.3055489
DO - 10.1145/3055399.3055489
M3 - Conference contribution
AN - SCOPUS:85024384539
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 461
EP - 473
BT - STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
A2 - McKenzie, Pierre
A2 - King, Valerie
A2 - Hatami, Hamed
PB - Association for Computing Machinery
T2 - 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
Y2 - 19 June 2017 through 23 June 2017
ER -