@inproceedings{2470eb806585411d8ad8d97cb07dfa1b,
title = "Extreme enumeration on GPU and in clouds - How many dollars you need to break SVP challenges",
abstract = "The complexity of the Shortest Vector Problem (SVP) in lattices is directly related to the security of NTRU and the provable level of security of many recently proposed lattice-based cryptosystems. We integrate several recent algorithmic improvements for solving SVP and take first place at dimension 120 in the SVP Challenge Hall of Fame. Our implementation allows us to find a short vector at dimension 114 using 8 NVIDIA video cards in less than two days. Specifically, our improvements to the recent Extreme Pruning in enumeration approach, proposed by Gama et al. in Eurocrypt 2010, include: (1) a more flexible bounding function in polynomial form; (2) code to take advantage of Clouds of commodity PCs (via the MapReduce framework); and (3) the use of NVIDIA's Graphics Processing Units (GPUs). We may now reasonably estimate the cost of a wide range of SVP instances in U.S. dollars, as rent paid to cloud-computing service providers, which is arguably a simpler and more practical measure of complexity.",
keywords = "Cloud Computing, Enumeration, Extreme Pruning, GPU, Shortest Vector Problem",
author = "Kuo, {Po Chun} and Michael Schneider and {\"O}zg{\"u}r Dagdelen and Jan Reichelt and Johannes Buchmann and Cheng, {Chen Mou} and Yang, {Bo Yin}",
year = "2011",
doi = "10.1007/978-3-642-23951-9_12",
language = "英语",
isbn = "9783642239502",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "176--191",
booktitle = "Cryptographic Hardware and Embedded Systems - 13th International Workshop, CHES 2011, Proceedings",
note = "13th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2011 ; Conference date: 28-09-2011 Through 01-10-2011",
}