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.

Participates in

Builds on Shortest Vector Problem

• GapSVP ⇒ LWE
• GapSVP ⇒ SIS