Random Sampling Revisited: Lattice Enumeration with Discrete Pruning

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 ellip-soid. 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.
Type de document :
Communication dans un congrès
EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Apr 2017, Paris, France. Springer International Publishing, Lecture Notes in Computer Science, 10211, pp.65 - 102, 2017, Advances in Cryptology – EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 – May 4, 2017, Proceedings, Part II
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01502051
Contributeur : Phong Q. Nguyen <>
Soumis le : mercredi 5 avril 2017 - 07:02:54
Dernière modification le : jeudi 15 juin 2017 - 09:09:24
Document(s) archivé(s) le : jeudi 6 juillet 2017 - 13:08:18

Fichier

Eprint-155.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01502051, version 1

Collections

Citation

Yoshinori Aono, Phong Q. Nguyen. Random Sampling Revisited: Lattice Enumeration with Discrete Pruning. EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Apr 2017, Paris, France. Springer International Publishing, Lecture Notes in Computer Science, 10211, pp.65 - 102, 2017, Advances in Cryptology – EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 – May 4, 2017, Proceedings, Part II. 〈hal-01502051〉

Partager

Métriques

Consultations de la notice

158

Téléchargements de fichiers

132