Shortest Vector Problem

The promise problem of deciding, given a lattice basis and a parameter $d$, whether the lattice’s shortest nonzero vector is shorter than $d$ or longer than $\gamma \cdot d$, for an approximation factor $\gamma$.

TODO: syntax and security definition.

Variations

A larger approximation factor makes the promise problem easier, so a containment proved for ${\mathrm{GapSVP}}_{\gamma }$ holds for every ${\gamma }^{\prime }\ge \gamma$ — standard.

Factor square root of n

${\mathrm{GapSVP}}_{\gamma }$ for $\gamma (n)\ge c\sqrt{n}$, where $c$ is the suitable absolute constant for which ${\mathrm{GapSVP}}_{c\sqrt{n}}$ lies in $\mathbf{coNP}$ — AR04. The theorem does not give $c=1$.

Factor square root of n over log n

${\mathrm{GapSVP}}_{\gamma }$ for $\gamma (n)\ge c\sqrt{n/\log n}$ for some constant $c>0$, the regime in which it lies in $\mathbf{coAM}$ — GG00.

Polynomial factors

GapSVP is hard for polynomial factors if for every constant $c>0$ no probabilistic polynomial-time classical algorithm solves ${\mathrm{GapSVP}}_{n^c}$ in the worst case: for every such algorithm and all sufficiently large $n$ there are a basis of an $n$-dimensional lattice $L$ and $d>0$ with ${\lambda }_1(L)\le d$ or ${\lambda }_1(L)>n^{c}d$ on which it answers wrongly with probability above $1/3$. Worst-case hardness of approximating GapSVP to within small polynomial factors is the hypothesis of the classical reductions to LWE — Pei09, BLPRS13.

Polynomial factors against quantum algorithms

GapSVP is quantumly hard for polynomial factors if for every constant $c>0$ no polynomial-time quantum algorithm solves ${\mathrm{GapSVP}}_{n^c}$ in the worst case: for every such algorithm and all sufficiently large $n$ there are a basis of an $n$-dimensional lattice $L$ and $d>0$ with ${\lambda }_1(L)\le d$ or ${\lambda }_1(L)>n^{c}d$ on which it answers wrongly with probability above $1/3$. This is the hypothesis of the quantum reduction to LWE — Reg05.

Participates in

Builds on Shortest Vector Problem

• Quantum polynomial-factor GapSVP ⇒ GapSVP for polynomial factors (via Polynomial factors against quantum algorithms)
• GapSVP for polynomial factors ⇒ GapSVP (via Polynomial factors)
• Polynomial-factor GapSVP ⇒ LWE (polynomial modulus) (via Polynomial factors)
• Polynomial-factor GapSVP ⇒ LWE (exponential modulus) (via Polynomial factors)
• log n) (via Factor square root of n over log n)
• GapSVP ∈ coNP for γ ≥ c√n (via Factor square root of n)
• Quantum polynomial-factor GapSVP ⇒ LWE (via Polynomial factors against quantum algorithms)
• GapSVP ∈ NP
• Polynomial-factor GapSVP ⇒ SIS (via Polynomial factors)
• log n) (via Factor square root of n over log n)

Produces Shortest Vector Problem

• Quantum polynomial-factor GapSVP ⇒ GapSVP for polynomial factors (via Polynomial factors)
• GapSVP for polynomial factors ⇒ GapSVP

Barriers

• No Karp reduction from NP to GapSVP for γ ≥ c√n unless NP = coNP (via Factor square root of n)
• log n) unless coNP ⊆ AM (via Factor square root of n over log n)