Cryptology ePrint Archive: Report 2020/120

The randomized slicer for CVPP: sharper, faster, smaller, batchier

Léo Ducas and 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 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.

Category / Keywords: foundations / lattices, closest vector problem with preprocessing, approximate Voronoi cells, iterative slicer, graph-based nearest neighbours

Original Publication (in the same form): IACR-PKC-2020

Date: received 5 Feb 2020, last revised 5 Feb 2020

Contact author: wvw at cwi nl

Available format(s): PDF | BibTeX Citation

Version: 20200206:144652 (All versions of this report)

Short URL: ia.cr/2020/120


[ Cryptology ePrint archive ]