No Karp reduction from NP to GapSVP for γ ≥ c√n unless NP = coNP

Unconditional · AR04

Statement

For $\gamma =c\sqrt{n}$ with AR04’s suitable constant $c$, ${\mathrm{GapSVP}}_{\gamma }$ (GapSVP) and ${\mathrm{GapCVP}}_{\gamma }$ lie in $\mathbf{NP}\cap \mathbf{coNP}$ (GapSVP ∈ coNP) — AR04. A Karp reduction from an $\mathbf{NP}$-complete problem to a promise problem in $\mathbf{coNP}$ places that problem in $\mathbf{coNP}$, so these problems are not $\mathbf{NP}$-hard under Karp reductions unless $\mathbf{NP}=\mathbf{coNP}$ — standard.

Notes

• The consequence concerns worst-case $\mathbf{NP}$-hardness of the lattice problem; it says nothing about the average-case hardness that LWE and SIS inherit from it — folklore.