Oplossen van het Shortest Vector Problem in $2^{0.6039n}$ tijd via Mid-point Hessian

Samenvatting

We presenteren gerandomiseerde algoritmen voor het shortest vector problem (SVP). Voor een $n$-dimensionaal rooster $\mathcal L$ lossen onze algoritmen SVP op in een klassieke tijd van $2^{0.6039n+o(n)}$ en een quantumtijd van $2^{0.5411n+o(n)}$, met een ruimtebeslag van $2^{0.5n+o(n)}$. Dit is een verbetering ten opzichte van het voorheen beste algoritme van Aggarwal, Dadush, Regev en Stephens-Davidowitz [STOC'15], dat een tijds- en ruimtecomplexiteit van $2^{n+o(n)}$ had.

Onze algoritmen maken intensief gebruik van de eigenschappen van de Hessiaan van de periodieke Gaussische functie bij de helft van de kortste vector: voor een kortste vector $v \in \mathcal L$ heeft de Hessiaan op $v/2$ een eigenvector die dicht bij $v$ ligt. Deze kan worden gebruikt om $v$ te herstellen met behulp van het bounded distance decoding-algoritme (preprocessing). Gegeven de periodiciteit modulo $\mathcal L$, worden de kandidaat-middelpunten geïndexeerd door de pariteitsklassen in $\mathcal L/2\mathcal L$. Ons algoritme zoekt naar de klasse van een kortste vector door de overeenkomstige Hessiaan te schatten met behulp van discrete Gaussische monsters.

We optimaliseren het algoritme met behulp van willekeurige subrooster-cosets en diverse samplingtechnieken, waarmee de uiteindelijke complexiteit wordt bereikt. De gehanteerde optimalisatietechnieken kunnen mogelijk ook onafhankelijk van dit probleem van belang zijn.