Paper 2017/017

Improved Algorithms for the Approximate k-List Problem in Euclidean Norm

Gottfried Herold and Elena Kirshanova

Abstract

We present an algorithm for the approximate $k$-List problem for the Euclidean distance that improves upon the Bai-Laarhoven-Stehle (BLS) algorithm from ANTS'16. The improvement stems from the observation that almost all the solutions to the approximate $k$-List problem form a particular configuration in $n$-dimensional space. Due to special properties of configurations, it is much easier to verify whether a $k$-tuple forms a configuration rather than checking whether it gives a solution to the $k$-List problem. Thus, phrasing the $k$-List problem as a problem of finding such configurations immediately gives a better algorithm. Furthermore, the search for configurations can be sped up using techniques from Locality-Sensitive Hashing (LSH). Stated in terms of configuration-search, our LSH-like algorithm offers a broader picture on previous LSH algorithms. For the Shortest Vector Problem, our configuration-search algorithm results in an exponential improvement for memory-efficient sieving algorithms. For $$, it allows us to bring down the complexity of the BLS sieve algorithm on an $$-dimensional lattice from $$ to $$ with the same space-requirement $$. Note that our algorithm beats the Gauss Sieve algorithm with time resp. space requirements of $$ resp. $$, while being easy to implement. Using LSH techniques, we can further reduce the time complexity down to $$ while retaining a memory complexity of $$.

Note: Full version of PKC paper.