GapSVP ∈ coNP for γ ≥ c√n

Inclusion · AR04

Statement

For $\gamma =c\sqrt{n}$ with a suitable constant $c$, ${\mathrm{GapSVP}}_{\gamma }$ (GapSVP), and likewise ${\mathrm{GapCVP}}_{\gamma }$, lies in coNP, hence in $\mathbf{NP}\cap \mathbf{coNP}$ — AR04.

Notes

• The factor-$\sqrt{n/\log n}$ problem is in $\mathbf{NP}\cap \mathbf{coAM}$ (GapSVP ∈ coAM) — GG00.
• Consequently ${\mathrm{GapSVP}}_{c\sqrt{n}}$ is not $\mathbf{NP}$-hard under Karp reductions unless $\mathbf{NP}=\mathbf{coNP}$: No Karp reduction from NP to GapSVPc√n — AR04.
• Regev’s reduction bases LWE with noise rate $\alpha <1$ on approximation factor $\gamma =\tilde{O}(n/\alpha )$, which exceeds $c\sqrt{n}$ (GapSVP ⇒ LWE) — Reg05. LWE-based cryptography therefore rests on worst-case lattice problems in $\mathbf{NP}\cap \mathbf{coNP}$, which are not $\mathbf{NP}$-hard under Karp reductions unless $\mathbf{NP}=\mathbf{coNP}$ — AR04.