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 root 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 root n is in NP boolean AND coAM. Thus, it seems unlikely that approximating these problems to within a root n factor is NP-hard. Previously, for the CVP (resp., SVP) problem, Lagarias et al. (1990, Combinatorica 10, 333-348), Hastad (1988, Combinatorica 8, 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 boolean AND coNP. On the other hand, Arora ci ill. (1997, J. Comput. System Sci. 54, 317-331) showed that the gap problem corresponding to approximating CVP within 2(log0.999 n) is quasi-NP-hard. (C) 2000 Academic Press.