Extreme Enumeration on GPU and in Clouds

The complexity of SVP (Shortest Vector Problem) 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 rst, second, and third place repectively at dimension 120, 116, and 114 on the SVP Challenge Hall of Fame.
Speci cally, our improvements to the recent Extreme Pruning in enumeration approach include a better set of pruning rules, code to take advantage of Clouds of commodity PCs (via the MapReduce framework), and the use of NVIDIA''s Graphics Processing Units (GPUs). We may now reasonably estimate the cost of a wide range of SVPs in U.S. dollars, as rent paid to cloud-computing service providers, which is arguably a simpler and more practical measure of complexity.
Our implementation allows us to fi nd a short vector at dimension 116 and 114 using 8 nVidia video cards in less than two days. As shown the price of security level, we spend 2300 U.S. dollar for renting machines from Amazon and solve SVP with dimension 120.