TY - GEN
T1 - The Randomized Slicer for CVPP
T2 - 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, PKC 2020
AU - Ducas, Léo
AU - Laarhoven, Thijs
AU - van Woerden, Wessel P.J.
PY - 2020
Y1 - 2020
N2 - 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 memory, we can solve a single CVPP instance in 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 memory, we can heuristically solve CVPP instances in amortized time, for batches of size at least. 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.
AB - 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 memory, we can solve a single CVPP instance in 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 memory, we can heuristically solve CVPP instances in amortized time, for batches of size at least. 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.
KW - Approximate Voronoi cells
KW - Closest vector problem with preprocessing
KW - Graph-based nearest neighbours
KW - Iterative slicer
KW - Lattices
UR - http://www.scopus.com/inward/record.url?scp=85090001706&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-45388-6_1
DO - 10.1007/978-3-030-45388-6_1
M3 - Conference contribution
AN - SCOPUS:85090001706
SN - 9783030453879
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 3
EP - 36
BT - Public-Key Cryptography – PKC 2020 - 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
A2 - Kiayias, Aggelos
A2 - Kohlweiss, Markulf
A2 - Wallden, Petros
A2 - Zikas, Vassilis
PB - Springer Gabler
Y2 - 4 May 2020 through 7 May 2020
ER -