Progressive lattice sieving

Thijs Laarhoven, Artur Mariano

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

10 Citaten (Scopus)

Samenvatting

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.

Originele taal-2Engels
TitelPost-Quantum Cryptography
Subtitel9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings
RedacteurenT. Lange, R. Steinwandt
Plaats van productieDordrecht
UitgeverijSpringer
Pagina's292-311
Aantal pagina's20
ISBN van elektronische versie978-3-319-79063-3
ISBN van geprinte versie978-3-319-79062-6
DOI's
StatusGepubliceerd - 1 jan 2018
Evenement9th International Conference on Post-Quantum Cryptography (PQCrypto 2018) - Fort Lauderdale, Verenigde Staten van Amerika
Duur: 9 apr 201811 apr 2018
Congresnummer: 9

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10786 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres9th International Conference on Post-Quantum Cryptography (PQCrypto 2018)
Verkorte titelPQCrypto 2018
LandVerenigde Staten van Amerika
StadFort Lauderdale
Periode9/04/1811/04/18

Vingerafdruk Duik in de onderzoeksthema's van 'Progressive lattice sieving'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Laarhoven, T., & Mariano, A. (2018). Progressive lattice sieving. In T. Lange, & R. Steinwandt (editors), Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings (blz. 292-311). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10786 LNCS). Springer. https://doi.org/10.1007/978-3-319-79063-3_14