On the Limits of Nonapproximability of Lattice Problems
On the Limits of Nonapproximability of Lattice Problems
复制标题
DOI：
10.1006/jcss.1999.1686
复制
发表时间：
2000-06
期刊：
影响因子：
--
通讯作者：
Oded Goldreich;S. Goldwasser
中科院分区：
文献类型：
--
作者：
Oded Goldreich;S. Goldwasser
我们给出了一个简单的常数轮交互证明系统，用于捕获整数格中优化问题的逼近度，特别是最近向量问题(CVP)和最短向量问题(SVP)。这些交互证明是针对CoNP方向的；即，我们给出了一个交互协议，证明了一个向量远离格(对于CVP)和一个交互协议，证明了最短格向量是长的(对于SVP)。此外，这些交互证明系统是诚实验证者完美零知识。我们得出结论，在n的因子内近似CVP(即SVP)是在NP？CoAM中的。因此，将这些问题近似到n个因素之内似乎不太可能是NP难的。以前，对于CVP(分别为SVP)问题，Lagarias等人。(1990，Combinatorica10,333？348)，Hastad(1988，Combinatorica8，75？81)和Banaszczyk(1993，Math.Annal.296,625？635)指出，对应于在n内近似CVP(分别为SVP)的间隙问题是NP？coNP。另一方面，Arora等人。(1997，J.Comput.系统科学54,317？331)表明，在2log0.999n内近似CVP所对应的间隙问题是准NP-难的。
We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of n, of optimization problems in integer lattices, specifically, the closest vector problem (CVP) and the shortest vector problem (SVP). These interactive proofs are for the coNP direction; that is, we give an interactive protocol showing that a vector is far from the lattice (for CVP) and an interactive protocol showing that the shortest-lattice-vector is long (for SVP). Furthermore, these interactive proof systems are honest-verifier perfect zero-knowledge. We conclude that approximating CVP (resp., SVP) within a factor of n is in NP?coAM. Thus, it seems unlikely that approximating these problems to within a n factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al. (1990, Combinatorica10, 333?348), Hastad (1988, Combinatorica8, 75?81), and Banaszczyk (1993, Math. Annal.296, 625?635) showed that the gap problem corresponding to approximating CVP (resp., SVP) within n is in NP?coNP. On the other hand, Arora et al. (1997, J. Comput. System Sci.54, 317?331) showed that the gap problem corresponding to approximating CVP within 2log0.999n is quasi-NP-hard.