Welcome to the resource topic for 2019/1028
Title:
Faster Sieving Algorithm for Approximate SVP with Constant Approximation Factors
Authors: Divesh Aggarwal, Bogdan Ursu, Serge Vaudenay
Abstract:Abstract. There is a large gap between theory and practice in the complexities of sieving algorithms for solving the shortest vector problem in an arbitrary Euclidean lattice. In this paper, we work towards reducing this gap, providing theoretical refinements of the time and space complexity bounds in the context of the approximate shortest vector problem. This is achieved by relaxing the requirements on the AKS algorithm, rather than on the ListSieve, resulting in exponentially smaller bounds starting from \mu\approx 2, for constant values of \mu. We also explain why these improvements carry over to also give the fastest quantum algorithms for the approximate shortest vector problem.
ePrint: https://eprint.iacr.org/2019/1028
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 .