GapSVP ∈ coAM for γ ≥ √(n/log n)

Inclusion · GG00

Statement

For $\gamma =c\sqrt{n/\log n}$ with any constant $c>0$, ${\mathrm{GapSVP}}_{\gamma }$ (GapSVP), and likewise ${\mathrm{GapCVP}}_{\gamma }$, lies in coAM: there is a constant-round interactive proof that the shortest nonzero vector is long — GG00.

Sketch

For GapCVP with distance bound $d$, the verifier picks $b\stackrel{\$}{\leftarrow }\{0,1\}$ and $r$ uniform in a ball of radius $\gamma d/2$, and sends $bt+r$ reduced modulo the lattice’s fundamental parallelepiped. On a no-instance the two balls are disjoint and the prover tells $b$; on a yes-instance their overlap is a $1/\mathrm{poly}(n)$ fraction of their volume, so every prover errs with noticeable probability, and repetition amplifies the gap. The protocol is honest-verifier perfect zero-knowledge, and the private-coin protocol becomes public-coin by GS86 — GG00.

Notes

• Statistical zero-knowledge proofs for ${\mathrm{GapSVP}}_{\gamma }$ itself, the $\mathbf{NP}$ direction, have a prover that is efficient given a short lattice vector: GapSVP ∈ SZK — MV03.
• Hence ${\mathrm{GapSVP}}_{\sqrt{n/\log n}}$ is not $\mathbf{NP}$-hard under Karp reductions unless the polynomial hierarchy collapses: log n) — GG00, BHZ87.