Finding closest lattice vectors using approximate voronoi cells

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

7 Citaten (Scopus)


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.

Originele taal-2Engels
TitelPost-Quantum Cryptography - 10th International Conference, PQCrypto 2019, Revised Selected Papers
RedacteurenJintai Ding, Rainer Steinwandt
Plaats van productieCham
Aantal pagina's20
ISBN van elektronische versie978-3-030-25510-7
ISBN van geprinte versie978-3-030-25509-1
StatusGepubliceerd - 1 jan 2019
Evenement10th International Conference on Post-Quantum Cryptography, PQCrypto 2019 - Chongquin, China
Duur: 8 mei 201910 mei 2019

Publicatie series

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


Congres10th International Conference on Post-Quantum Cryptography, PQCrypto 2019

Vingerafdruk Duik in de onderzoeksthema's van 'Finding closest lattice vectors using approximate voronoi cells'. Samen vormen ze een unieke vingerafdruk.

Citeer dit