Progressive lattice sieving

Thijs Laarhoven, Artur Mariano

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

15 Citations (Scopus)

Abstract

Most algorithms for hard lattice problems are based on the principle of rank reduction: to solve a problem in a d-dimensional lattice, one first solves one or more problem instances in a sublattice of rank d–1, and then uses this information to find a solution to the original problem. Existing lattice sieving methods, however, tackle lattice problems such as the shortest vector problem (SVP) directly, and work with the full-rank lattice from the start. Lattice sieving further seems to benefit less from starting with reduced bases than other methods, and finding an approximate solution almost takes as long as finding an exact solution. These properties currently set sieving apart from other methods. In this work we consider a progressive approach to lattice sieving, where we gradually introduce new basis vectors only when the sieve has stabilized on the previous basis vectors. This leads to improved (heuristic) guarantees on finding approximate shortest vectors, a bigger practical impact of the quality of the basis on the run-time, better memory management, a smoother and more predictable behavior of the algorithm, and significantly faster convergence – compared to traditional approaches, we save between a factor 20 to 40 in the time complexity for SVP.

Original languageEnglish
Title of host publicationPost-Quantum Cryptography
Subtitle of host publication9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings
EditorsT. Lange, R. Steinwandt
Place of PublicationDordrecht
PublisherSpringer
Pages292-311
Number of pages20
ISBN (Electronic)978-3-319-79063-3
ISBN (Print)978-3-319-79062-6
DOIs
Publication statusPublished - 1 Jan 2018
Event9th International Conference on Post-Quantum Cryptography (PQCrypto 2018) - Fort Lauderdale, United States
Duration: 9 Apr 201811 Apr 2018
Conference number: 9

Publication series

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

Conference

Conference9th International Conference on Post-Quantum Cryptography (PQCrypto 2018)
Abbreviated titlePQCrypto 2018
CountryUnited States
CityFort Lauderdale
Period9/04/1811/04/18

Keywords

  • Lattice sieving
  • Lattice-based cryptography
  • Nearest neighbor searching
  • Shortest vector problem (SVP)

Fingerprint Dive into the research topics of 'Progressive lattice sieving'. Together they form a unique fingerprint.

Cite this