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

Inclusion · MV03

Statement

For $\gamma =c\sqrt{n/\log n}$, ${\mathrm{GapSVP}}_{\gamma }$ (GapSVP) and ${\mathrm{GapCVP}}_{\gamma }$ have statistical zero-knowledge proofs whose provers are efficient given an $\mathbf{NP}$ witness, a short lattice vector or, for GapCVP, a lattice vector close to the target — MV03.

Notes

• The Goldreich–Goldwasser protocol places the complement in $\mathbf{HVSZK}$, which equals $\mathbf{SZK}$ (HVSZK = SZK), and closure under complement then places the problem itself in $\mathbf{SZK}$; MV03’s contribution is the efficient prover — GG00, GSV98, Oka96, MV03.
• Since $\mathbf{SZK}\subseteq \mathbf{AM}\cap \mathbf{coAM}$ (SZK ⊆ AM, SZK ⊆ coAM), the problem is not $\mathbf{NP}$-hard under Karp reductions unless the polynomial hierarchy collapses — BHZ87.