We show simple constant-round interactive proof systems for
problems capturing the approximability, to within a factor of \sqrt{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 \sqrt{n} is in NP\cap coAM.
Thus, it seems unlikely that approximating these problems
to within a \sqrt{n} factor is NP-hard.
Previously, for the CVP (resp., SVP) problem,
Lagarias et al, Hastad and Banaszczyk showed
that the gap problem corresponding to
approximating CVP (resp., SVP) within n is in NP\cap\coNP.
On the other hand, Arora et al showed that the gap problem corresponding
to approximating CVP within 2^{\log^{0.999}n} is quasi-NP-hard.

We show simple constant-round interactive proof systems for
problems capturing the approximability, to within a factor of \sqrt{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 \sqrt{n} is in NP\cap coAM.
Thus, it seems unlikely that approximating these problems
to within a \sqrt{n} factor is NP-hard.
Previously, for the CVP (resp., SVP) problem,
Lagarias et al, Hastad and Banaszczyk showed
that the gap problem corresponding to
approximating CVP (resp., SVP) within n is in NP\cap\coNP.
On the other hand, Arora et al showed that the gap problem corresponding
to approximating CVP within 2^{\log^{0.999}n} is quasi-NP-hard.

We show simple constant-round interactive proof systems for
problems capturing the approximability, to within a factor of \sqrt{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 \sqrt{n} is in NP\cap coAM.
Thus, it seems unlikely that approximating these problems
to within a \sqrt{n} factor is NP-hard.
Previously, for the CVP (resp., SVP) problem, Lagarias et al showed
that the gap problem corresponding to approximating CVP within n^{1.5}
(resp., approximating SVP within n) is in NP\cap coNP.
On the other hand, Arora et al showed that the gap problem corresponding
to approximating CVP within 2^{\log^{0.499}n} is quasi-NP-hard.