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.