On the complexity of lattice problems with polynomial approximation factors

Research output: Chapter in Book/Report/Conference proceedingChapter

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 languageEnglish (US)
Title of host publicationInformation Security and Cryptography
PublisherSpringer International Publishing
Pages475-496
Number of pages22
DOIs
StatePublished - 2010

Publication series

NameInformation Security and Cryptography
Volume10
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

Fingerprint Dive into the research topics of 'On the complexity of lattice problems with polynomial approximation factors'. Together they form a unique fingerprint.

  • Cite this

    Regev, O. (2010). On the complexity of lattice problems with polynomial approximation factors. In Information Security and Cryptography (pp. 475-496). (Information Security and Cryptography; Vol. 10). Springer International Publishing. https://doi.org/10.1007/978-3-642-02295-1_15