Sieving for closest lattice vectors (with preprocessing)

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)
36 Downloads (Pure)

Abstract

Lattice-based cryptography has recently emerged as a prime candidate for efficient and secure post-quantum cryptography. The two main hard problems underlying its security are the shortest vector problem (SVP) and the closest vector problem (CVP). Various algorithms have been studied for solving these problems, and for SVP, lattice sieving currently dominates in terms of the asymptotic time complexity: one can heuristically solve SVP in time $2^{0.292d}$ in high dimensions $d$ [BDGL'16]. Although several SVP algorithms can also be used to solve CVP, it is not clear whether this also holds for heuristic lattice sieving methods. The best time complexity for CVP is currently $2^{0.377d}$ [BGJ'14]. In this paper we revisit sieving algorithms for solving SVP, and study how these algorithms can be modified to solve CVP and its variants as well. Our first method is aimed at solving one problem instance and minimizes the overall time complexity for a single CVP instance with a time complexity of $2^{0.292d}$. Our second method minimizes the amortized time complexity for several instances on the same lattice, at the cost of a larger preprocessing cost. We can solve the closest vector problem with preprocessing (CVPP) with $2^{0.636d}$ space and preprocessing, in $2^{0.136d}$ time, while the query complexity can even be reduced to $2^{\epsilon d}$ at the cost of preprocessing time and memory complexities of $(1/\epsilon)^{O(d)}$. For easier variants of CVP, such as approximate CVP and bounded distance decoding (BDD), we further show how the preprocessing method achieves even better complexities. For instance, we can solve approximate CVPP with large approximation factors $k$ with polynomial-sized advice in polynomial time if $k = \Omega(\sqrt{d/\log d})$, heuristically closing the gap between the decision-CVPP result of [AR'04] and the search-CVPP result of [DRS'14].
Original languageEnglish
Title of host publicationSelected Areas in Cryptography – SAC 2016
Subtitle of host publication23rd International Conference, St. John's, NL, Canada, August 10-12, 2016, Revised Selected Papers
EditorsR. Avanzi, H. Heys
Place of PublicationDordrecht
PublisherSpringer
Pages533-542
ISBN (Electronic)978-3-319-69453-5
ISBN (Print)978-3-319-69452-8
DOIs
Publication statusPublished - 16 Jul 2016
Event23rd International Conference on Selected Areas in Cryptography (SAC 2016) - St. John's, Canada
Duration: 10 Aug 201612 Aug 2016
Conference number: 23

Publication series

NameLNCS
Volume10532

Conference

Conference23rd International Conference on Selected Areas in Cryptography (SAC 2016)
Abbreviated titleSAC 2016
CountryCanada
CitySt. John's
Period10/08/1612/08/16

Keywords

  • cs.CR
  • cs.CG

Fingerprint Dive into the research topics of 'Sieving for closest lattice vectors (with preprocessing)'. Together they form a unique fingerprint.

Cite this