On the Limits of Nonapproximability of Lattice Problems

摘要

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), Håstad (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.