2020 | OriginalPaper | Buchkapitel
The Randomized Slicer for CVPP: Sharper, Faster, Smaller, Batchier
verfasst von : Léo Ducas, Thijs Laarhoven, Wessel P. J. van Woerden
Erschienen in: Public-Key Cryptography – PKC 2020
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
-
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)}\).