Improved Algorithms for the Approximate k-List Problem in Euclidean Norm
Gottfried Herold and Elena Kirshanova
Abstract
We present an algorithm for the approximate -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 -List problem form a particular configuration in -dimensional space. Due to special properties of configurations, it is much easier to verify whether a -tuple forms a configuration rather than checking whether it gives a solution to the -List problem. Thus, phrasing the -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 .
@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},
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.