Extreme enumeration on GPU and in clouds - How many dollars you need to break SVP challenges

Po Chun Kuo*, Michael Schneider, Özgür Dagdelen, Jan Reichelt, Johannes Buchmann, Chen Mou Cheng, Bo Yin Yang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

28 Scopus citations

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.

Original languageEnglish
Title of host publicationCryptographic Hardware and Embedded Systems - 13th International Workshop, CHES 2011, Proceedings
Pages176-191
Number of pages16
DOIs
StatePublished - 2011
Externally publishedYes
Event13th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2011 - Nara, Japan
Duration: 28 09 201101 10 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6917 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2011
Country/TerritoryJapan
CityNara
Period28/09/1101/10/11

Keywords

  • Cloud Computing
  • Enumeration
  • Extreme Pruning
  • GPU
  • Shortest Vector Problem

Fingerprint

Dive into the research topics of 'Extreme enumeration on GPU and in clouds - How many dollars you need to break SVP challenges'. Together they form a unique fingerprint.

Cite this