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 $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)}$.

Note: Full version of PKC paper.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in PKC 2017
Keywords
latticesk-list problemsievingSVPcryptanalysis
Contact author(s)
gottfried herold @ rub de
History
2017-01-26: revised
2017-01-11: received
See all versions
Short URL
https://ia.cr/2017/017
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/017,
      author = {Gottfried Herold and Elena Kirshanova},
      title = {Improved Algorithms for the Approximate k-List Problem in Euclidean Norm},
      howpublished = {Cryptology ePrint Archive, Paper 2017/017},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/017}},
      url = {https://eprint.iacr.org/2017/017}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.