TY - CHAP
T1 - On the complexity of lattice problems with polynomial approximation factors
AU - Regev, Oded
N1 - Funding Information:
This chapter is partly based on lecture notes scribed by Michael Khanevsky as well as on the paper [24] coauthored with Dorit Aharonov. I thank Ishay Haviv and the anonymous reviewers for their comments on an earlier draft. I also thank DanieleMicciancio for pointing out that the argument in Section “NP-Hardness ” extends to the search version. Supported by the Binational Science Foundation, by the Israel Science Foundation, by the European Commission under the Integrated Project QAP funded by the IST directorate as Contract Number 015848, and by a European Research Council (ERC) Starting Grant.
Publisher Copyright:
© 2009, Springer-Verlag Berlin Heidelberg.
PY - 2010
Y1 - 2010
N2 - Lattice problems are known to be hard to approximate to withinsub-polynomial factors. For larger approximation factors, such as √n, lattice problems are known to be in complexity classes, such as NP ∩ coNP, and are hence unlikely to be NP-hard. Here, we survey known results in this area. We also discuss some related zero-knowledge protocols for lattice problems.
AB - Lattice problems are known to be hard to approximate to withinsub-polynomial factors. For larger approximation factors, such as √n, lattice problems are known to be in complexity classes, such as NP ∩ coNP, and are hence unlikely to be NP-hard. Here, we survey known results in this area. We also discuss some related zero-knowledge protocols for lattice problems.
UR - http://www.scopus.com/inward/record.url?scp=84883319179&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84883319179&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02295-1_15
DO - 10.1007/978-3-642-02295-1_15
M3 - Chapter
AN - SCOPUS:84883319179
T3 - Information Security and Cryptography
SP - 475
EP - 496
BT - Information Security and Cryptography
PB - Springer International Publishing
ER -