Short(est) Vector Problem SVP

• Eingabe: (eine Basis B für) ein Gitter Γ , eine Zahl D
• Ausgabe:

  ein Vektor v∈Γ $\setminus$ {0} mit | v|≤D , falls existiert.

  Beweis für v∈Γ durch c∈$\mathbb {Z}$^d mit v = c⋅B

Komplexität ist hoch

• man kann damit Geheimnisse verstecken
• effiziente Näherungsverfahren sind interessant

Anwendungen (außer Krypt.) bei

• Faktorisieren v. Polynomen , • ganzzahliger Optimierung
• Bestimmen von (Minimal)Polynomen für algebraische Zahlen, die nur numerisch approximiert vorliegen