Paper 2020/120
The randomized slicer for CVPP: sharper, faster, smaller, batchier
Léo Ducas, Thijs Laarhoven, and Wessel P. J. van Woerden
Abstract
Following the recent line of work on solving the closest vector problem with preprocessing (CVPP) using approximate Voronoi cells, we improve upon previous results in the following ways:  We derive sharp asymptotic bounds on the success probability of the randomized slicer, by modelling the behaviour of the algorithm as a random walk on the coset of the lattice of the target vector. We thereby solve the open question left by DoulgerakisLaarhovenDe Weger [PQCrypto 2019] and Laarhoven~[MathCrypt 2019].  We obtain better tradeoffs for CVPP and its generalisations (strictly, in certain regimes), both with and without nearest neighbour searching, as a direct result of the above sharp bounds on the success probabilities.  We show how to reduce the memory requirement of the slicer, and in particular the corresponding nearest neighbour data structures, using ideas similar to those proposed by BeckerGamaJoux [Cryptology ePrint Archive, 2015]. Using $2^{0.185d + o(d)}$ memory, we can solve a single CVPP instance in $2^{0.264d + o(d)}$ time.  We further improve on the perinstance time complexities in certain memory regimes, when we are given a sufficiently large batch of CVPP problem instances for the same lattice. Using $2^{0.208d + o(d)}$ memory, we can heuristically solve CVPP instances in $2^{0.234d + o(d)}$ amortized time, for batches of size at least $2^{0.058d + o(d)}$. Our random walk model for analysing arbitrarystep transition probabilities in complex stepwise algorithms may be of independent interest, both for deriving analytic bounds through convexity arguments, and for computing optimal paths numerically with a shortest path algorithm. As a side result we apply the same random walk model to graphbased nearest neighbour searching, where we improve upon results of Laarhoven [SOCG 2018] by deriving sharp bounds on the success probability of the corresponding greedy search procedure.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published by the IACR in PKC 2020
 DOI
 10.1007/9783030453886_1
 Keywords
 latticesclosest vector problem with preprocessingapproximate Voronoi cellsiterative slicergraphbased nearest neighbours
 Contact author(s)
 wvw @ cwi nl
 History
 20201116: revised
 20200206: received
 See all versions
 Short URL
 https://ia.cr/2020/120
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/120, author = {Léo Ducas and Thijs Laarhoven and Wessel P. J. van Woerden}, title = {The randomized slicer for {CVPP}: sharper, faster, smaller, batchier}, howpublished = {Cryptology ePrint Archive, Paper 2020/120}, year = {2020}, doi = {10.1007/9783030453886_1}, note = {\url{https://eprint.iacr.org/2020/120}}, url = {https://eprint.iacr.org/2020/120} }