Welcome to the resource topic for 2020/120
Title:
The randomized slicer for CVPP: sharper, faster, smaller, batchier
Authors: Léo Ducas, Thijs Laarhoven, 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 Doulgerakis–Laarhoven–De Weger [PQCrypto 2019] and Laarhoven~[MathCrypt 2019]. - We obtain better trade-offs 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 Becker–Gama–Joux [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 per-instance 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 arbitrary-step transition probabilities in complex step-wise 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 graph-based 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.
ePrint: https://eprint.iacr.org/2020/120
Talk: https://www.youtube.com/watch?v=3bkaM9J-p8c
Slides: https://iacr.org/submit/files/slides/2020/pkc/pkc2020/202/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .