Kürzester-Vektor-Problem in 2^{0,6039n} Zeit gelöst

Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-Point Hessian

Dieser Artikel stellt randomisierte Algorithmen für das Kürzeste-Vektor-Problem (SVP) vor. Für ein n-dimensionales Gitter L lösen sie SVP klassisch in 2^{0,6039n+o(n)} und quantenmechanisch in 2^{0,5411n+o(n)} Zeit, mit Speicherbedarf 2^{0,5n+o(n)}. Dies verbessert den bisher besten Algorithmus von Aggarwal, Dadush, Regev und Stephens-Davidowitz (STOC'15), der in 2^{n+o(n)} Zeit und Speicher läuft. Die Algorithmen nutzen die Hesse-Matrix der periodischen Gauß-Funktion am halben kürzesten Vektor: Für einen kürzesten Vektor v hat die Hesse-Matrix bei v/2 einen Eigenvektor nahe v, der zur Wiederherstellung von v mittels eines Bounded-Distance-Decoding-Algorithmus verwendet werden kann. Die Kandidaten-Mittelpunkte werden durch Paritätsklassen in L/2L indiziert. Der Algorithmus sucht die Klasse eines kürzesten Vektors, indem er die zugehörigen Hesse-Matrizen mit diskreten Gauß-Stichproben schätzt. Die Optimierung erfolgt durch zufällige Untergitter-Kosets und verschiedene Stichprobentechniken.