**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 $k=3$, it allows us to bring down the complexity of the BLS sieve algorithm on an $n$-dimensional lattice from $2^{0.4812n+o(n)}$ to $2^{0.3962n + o(n)}$ with the same space-requirement $2^{0.1887n + o(n)}$. Note that our algorithm beats the Gauss Sieve algorithm with time resp. space requirements of $2^{0.415n+o(n)}$ resp. $2^{0.208n + o(n)}$, while being easy to implement. Using LSH techniques, we can further reduce the time complexity down to $2^{0.3717n + o(n)}$ while retaining a memory complexity of $2^{0.1887n+o(n)}$.

**Category / Keywords: **lattices, k-list problem, sieving, SVP, cryptanalysis

**Original Publication**** (in the same form): **IACR-PKC-2017

**Date: **received 9 Jan 2017, last revised 26 Jan 2017

**Contact author: **gottfried herold at rub de

**Available format(s): **PDF | BibTeX Citation

**Note: **Full version of PKC paper.

**Version: **20170126:130509 (All versions of this report)

**Short URL: **ia.cr/2017/017

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]