Cryptology ePrint Archive: Report 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.
Category / Keywords: Lattices, Enumeration, Algorithms, Short Vectors, Public-key cryptanalysis
Original Publication (in the same form): IACR-EUROCRYPT-2017
Date: received 16 Feb 2017, last revised 22 Feb 2017
Contact author: Phong Nguyen at inria fr
Available format(s): PDF | BibTeX Citation
Note: This is the full version: some typos have been fixed.
Version: 20170223:031202 (All versions of this report)
Short URL: ia.cr/2017/155
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]