TY - CHAP

T1 - On the complexity of lattice problems with polynomial approximation factors

AU - Regev, Oded

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 -