Paper 2019/1028

Faster Sieving Algorithm for Approximate SVP with Constant Approximation Factors

Divesh Aggarwal, Bogdan Ursu, and 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
lattice techniques
Contact author(s)
bogdanbear @ gmail com
divesh aggarwal @ gmail com
serge vaudenay @ epfl ch
History
2019-09-11: received
Short URL
https://ia.cr/2019/1028
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1028,
      author = {Divesh Aggarwal and Bogdan Ursu and Serge Vaudenay},
      title = {Faster Sieving Algorithm for Approximate SVP with Constant Approximation Factors},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1028},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1028}},
      url = {https://eprint.iacr.org/2019/1028}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.