Finding closest lattice vectors using approximate voronoi cells

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

4 Citations (Scopus)

Abstract

The two traditional hard problems underlying the security of lattice-based cryptography are the shortest vector problem (SVP) and the closest vector problem (CVP). For a long time, lattice enumeration was considered the fastest method for solving these problems in high dimensions, but recent work on memory-intensive methods has resulted in lattice sieving overtaking enumeration both in theory and in practice. Some of the recent improvements [Ducas, Eurocrypt 2018; Laarhoven–Mariano, PQCrypto 2018; Albrecht–Ducas–Herold–Kirshanova–Postlethwaite–Stevens, 2018] are based on the fact that these methods find more than just one short lattice vector, and this additional data can be reused effectively later on to solve other, closely related problems faster. Similarly, results for the preprocessing version of CVP (CVPP) have demonstrated that once this initial data has been generated, instances of CVP can be solved faster than when solving them directly, albeit with worse memory complexities [Laarhoven, SAC 2016]. In this work we study CVPP in terms of approximate Voronoi cells, and obtain better time and space complexities using randomized slicing, which is similar in spirit to using randomized bases in lattice enumeration [Gama–Nguyen–Regev, Eurocrypt 2010]. With this approach, we improve upon the state-of-the-art complexities for CVPP, both theoretically and experimentally, with a practical speedup of several orders of magnitude compared to non-preprocessed SVP or CVP. Such a fast CVPP solver may give rise to faster enumeration methods, where the CVPP solver is used to replace the bottom part of the enumeration tree, consisting of a batch of CVP instances in the same lattice. Asymptotically, we further show that we can solve an exponential number of instances of CVP in a lattice in essentially the same amount of time and space as the fastest method for solving just one CVP instance. This is in line with various recent results, showing that perhaps the biggest strength of memory-intensive methods lies in being able to reuse the generated data several times. Similar to [Ducas, Eurocrypt 2018], this further means that we can achieve a “few dimensions for free” for sieving for SVP or CVP, by doing Θ(d/ log d) levels of enumeration on top of a CVPP solver based on approximate Voronoi cells.

Original languageEnglish
Title of host publicationPost-Quantum Cryptography - 10th International Conference, PQCrypto 2019, Revised Selected Papers
EditorsJintai Ding, Rainer Steinwandt
Place of PublicationCham
PublisherSpringer
Pages3-22
Number of pages20
ISBN (Electronic)978-3-030-25510-7
ISBN (Print)978-3-030-25509-1
DOIs
Publication statusPublished - 1 Jan 2019
Event10th International Conference on Post-Quantum Cryptography, PQCrypto 2019 - Chongquin, China
Duration: 8 May 201910 May 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11505 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Post-Quantum Cryptography, PQCrypto 2019
CountryChina
CityChongquin
Period8/05/1910/05/19

Keywords

  • Closest vector problem (CVP)
  • Lattices
  • Preprocessing
  • Shortest vector problem (SVP)
  • Sieving algorithms
  • Voronoi cells

Fingerprint Dive into the research topics of 'Finding closest lattice vectors using approximate voronoi cells'. Together they form a unique fingerprint.

  • Cite this

    Doulgerakis, E., Laarhoven, T., & de Weger, B. (2019). Finding closest lattice vectors using approximate voronoi cells. In J. Ding, & R. Steinwandt (Eds.), Post-Quantum Cryptography - 10th International Conference, PQCrypto 2019, Revised Selected Papers (pp. 3-22). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11505 LNCS). Springer. https://doi.org/10.1007/978-3-030-25510-7_1