|
Abstract : |
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., |
