Paper 2017/155

Random Sampling Revisited: Lattice Enumeration with Discrete Pruning

Yoshinori Aono and Phong Q. Nguyen

Abstract

In 2003, Schnorr introduced Random sampling to find very short lattice vectors, as an alternative to enumeration. An improved variant has been used in the past few years by Kashiwabara et al. to solve the largest Darmstadt SVP challenges. However, the behaviour of random sampling and its variants is not well-understood: all analyses so far rely on a questionable heuristic assumption, namely that the lattice vectors produced by some algorithm are uniformly distributed over certain parallelepipeds. In this paper, we introduce lattice enumeration with discrete pruning, which generalizes random sampling and its variants, and provides a novel geometric description based on partitions of the n-dimensional space. We obtain what is arguably the first sound analysis of random sampling, by showing how discrete pruning can be rigorously analyzed under the well-known Gaussian heuristic, in the same model as the Gama-Nguyen-Regev analysis of pruned enumeration from EUROCRYPT '10, albeit using different tools: we show how to efficiently compute the volume of the intersection of a ball with a box, and to efficiently approximate a large sum of many such volumes, based on statistical inference. Furthermore, we show how to select good parameters for discrete pruning by enumerating integer points in an ellipsoid. Our analysis is backed up by experiments and allows for the first time to reasonably estimate the success probability of random sampling and its variants, and to make comparisons with previous forms of pruned enumeration. Our work unifies random sampling and pruned enumeration and show that they are complementary of each other: both have different characteristics and offer different trade-offs to speed up enumeration.

Note: This is the full version: some typos have been fixed.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in EUROCRYPT 2017
Keywords
LatticesEnumerationAlgorithmsShort VectorsPublic-key cryptanalysis
Contact author(s)
Phong Nguyen @ inria fr
History
2017-02-23: revised
2017-02-22: received
See all versions
Short URL
https://ia.cr/2017/155
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/155,
      author = {Yoshinori Aono and Phong Q.  Nguyen},
      title = {Random Sampling Revisited: Lattice Enumeration with Discrete Pruning},
      howpublished = {Cryptology ePrint Archive, Paper 2017/155},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/155}},
      url = {https://eprint.iacr.org/2017/155}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.