On the complexity of lattice problems with polynomial approximation factors

Oded Regev

doi:10.1007/978-3-642-02295-1_15

On the complexity of lattice problems with polynomial approximation factors

Oded Regev

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

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.

Original language	English (US)
Title of host publication	Information Security and Cryptography
Publisher	Springer International Publishing
Pages	475-496
Number of pages	22
DOIs	https://doi.org/10.1007/978-3-642-02295-1_15
State	Published - 2010

Publication series

Name	Information Security and Cryptography
Volume	10
ISSN (Print)	1619-7100
ISSN (Electronic)	2197-845X

ASJC Scopus subject areas

Safety, Risk, Reliability and Quality
Computer Networks and Communications
Computational Theory and Mathematics
Information Systems and Management

Access to Document

10.1007/978-3-642-02295-1_15

Cite this

@inbook{861e8aafb7db4e798028eb1c3e318cc6,

title = "On the complexity of lattice problems with polynomial approximation factors",

abstract = "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.",

author = "Oded Regev",

note = "Publisher Copyright: {\textcopyright} 2009, Springer-Verlag Berlin Heidelberg.",

year = "2010",

doi = "10.1007/978-3-642-02295-1_15",

language = "English (US)",

series = "Information Security and Cryptography",

publisher = "Springer International Publishing",

pages = "475--496",

booktitle = "Information Security and Cryptography",

}

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 -

On the complexity of lattice problems with polynomial approximation factors

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this