Welcome to the resource topic for 2017/017
Title:
Improved Algorithms for the Approximate k-List Problem in Euclidean Norm
Authors: Gottfried Herold, 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)}.
ePrint: https://eprint.iacr.org/2017/017
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .