TU Darmstadt / ULB / TUbiblio

Computing Shortest Lattice Vectors on Special Hardware

Schneider, Michael (2011)
Computing Shortest Lattice Vectors on Special Hardware.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

The shortest vector problem (SVP) in lattices is related to problems in combinatorial optimization, algorithmic number theory, communication theory, and cryptography. In 1996, Ajtai published his breakthrough idea how to create lattice-based one-way functions based on the worst-case hardness of an approximate version of SVP. Worst-case hardness is one of the outstanding properties of all modern lattice-based cryptographic schemes. Furthermore, there are no sub-exponential time algorithms known solving SVP, even on potential, strong quantum computers. These facts distinguish the shortest vector problem as a good basis for modern cryptography. In order to theoretically assess the security of lattice-based cryptosystems, knowledge of the asymptotic runtime of SVP solvers is an important issue. For selection of practical parameters however, the average-case behaviour of these algorithms is at least as important. SVP solvers are applied as subroutine in so-called lattice basis reduction algorithms. These build the cornerstone of the fastest attacks on lattice-based cryptosystems. Therefore, improving SVP algorithms directly affects the fastest practical attacks on lattice-based cryptosystems. Building on existing serial SVP algorithms, this thesis presents multiple approaches towards estimating the practical hardness of the shortest vector problem. We employ various special hardware, ranging from multicore CPUs and graphics cards to “supercomputers” and compute clouds. We develop parallel algorithms and assess their practical running times and scalability. Among others, we present our parallel version of the Extreme Pruning Enumeration algorithm, the currently fastest SVP solver available worldwide. Our implementation set the current records in the SVP challenge, the mostly deployed public SVP solver competition. The influence of our work on the security of lattice-based cryptosystems is twofold. First, we help assessing the strength of worst-case problems that build the theoretical basement of lattice-based cryptography. Second, we show how to improve the fastest practical attacks on these systems in the average case. As further result, we present a variant of the sieving algorithm to solve the shortest vector problem in ideal lattices. Ideal lattices are the most important type of lattices in cryptography. Our algorithm is the first to exploit their special structure, allowing us to find shortest vectors faster than in regular lattices.

Typ des Eintrags: Dissertation
Erschienen: 2011
Autor(en): Schneider, Michael
Art des Eintrags: Erstveröffentlichung
Titel: Computing Shortest Lattice Vectors on Special Hardware
Sprache: Englisch
Referenten: Buchmann, Prof. Dr. Johannes ; Cheng, Prof. Dr. Chen-Mou
Publikationsjahr: 6 Dezember 2011
Datum der mündlichen Prüfung: 11 November 2011
URL / URN: urn:nbn:de:tuda-tuprints-28290
Zugehörige Links:
Kurzbeschreibung (Abstract):

The shortest vector problem (SVP) in lattices is related to problems in combinatorial optimization, algorithmic number theory, communication theory, and cryptography. In 1996, Ajtai published his breakthrough idea how to create lattice-based one-way functions based on the worst-case hardness of an approximate version of SVP. Worst-case hardness is one of the outstanding properties of all modern lattice-based cryptographic schemes. Furthermore, there are no sub-exponential time algorithms known solving SVP, even on potential, strong quantum computers. These facts distinguish the shortest vector problem as a good basis for modern cryptography. In order to theoretically assess the security of lattice-based cryptosystems, knowledge of the asymptotic runtime of SVP solvers is an important issue. For selection of practical parameters however, the average-case behaviour of these algorithms is at least as important. SVP solvers are applied as subroutine in so-called lattice basis reduction algorithms. These build the cornerstone of the fastest attacks on lattice-based cryptosystems. Therefore, improving SVP algorithms directly affects the fastest practical attacks on lattice-based cryptosystems. Building on existing serial SVP algorithms, this thesis presents multiple approaches towards estimating the practical hardness of the shortest vector problem. We employ various special hardware, ranging from multicore CPUs and graphics cards to “supercomputers” and compute clouds. We develop parallel algorithms and assess their practical running times and scalability. Among others, we present our parallel version of the Extreme Pruning Enumeration algorithm, the currently fastest SVP solver available worldwide. Our implementation set the current records in the SVP challenge, the mostly deployed public SVP solver competition. The influence of our work on the security of lattice-based cryptosystems is twofold. First, we help assessing the strength of worst-case problems that build the theoretical basement of lattice-based cryptography. Second, we show how to improve the fastest practical attacks on these systems in the average case. As further result, we present a variant of the sieving algorithm to solve the shortest vector problem in ideal lattices. Ideal lattices are the most important type of lattices in cryptography. Our algorithm is the first to exploit their special structure, allowing us to find shortest vectors faster than in regular lattices.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Schwere Berechnungsprobleme bilden die Grundlage für kryptographische Systeme. In der modernen Kryptographie wird versucht, das Spektrum dieser Probleme zu erweitern, und neben den bekannten wie dem Faktorisieren ganzer Zahlen werden neuartige Probleme betrachtet. Darunter befindet sich auch das Problem, kürzeste Vektoren in einem Gitter zu finden ("shortest vector problem" - SVP). Im Jahr 1996 veröffentlichte Ajtai seine bahnbrechende Idee zur Erstellung gitterbasierter Einweg-Funktionen auf der Grundlage einer approximativen Variante des SVP. Das Außergewöhnliche daran ist, dass das Lösen einer zufälligen Instanz des SVP beweisbar mindestens so schwer ist wie das Lösen der schwierigsten Instanzen eines verwandten Problems. Diese "worst-case hardness" ist eine der herausragenden Eigenschaften aller moderner, gitterbasierter Kryptographie-Verfahren. Darüber hinaus sind keine subexponentiellen Algorithmen zur Lösung des SVP bekannt, auch nicht für potenzielle Quantencomputer. Diese Tatsachen zeichnen das "shortest vector problem" als eine gute Grundlage für die moderne Kryptographie aus. Um die Sicherheit gitterbasierter Kryptosysteme theoretisch zu beurteilen, ist die Kenntnis der asymptotischen Laufzeit von SVP-Lösern wichtig. Nur so lässt sich feststellen, ob die Annahmen uber die Schwierigkeit von SVP gerechtfertigt sind. Für die Auswahl praktischer Parameter ist jedoch das durchschnittliche Laufzeitverhalten dieser Algorithmen ebenso wichtig. SVP-Löser werden als Unterprogramme in sogenannten Gitter-Reduktions-Algorithmen verwendet. Diese bilden die Basis der schnellsten praktischen Angriffe auf Kryptosysteme. Daher wirkt sich die Verbesserung von SVP Algorithmen hier direkt aus. Aufbauend auf den vorhandenen seriellen SVP-Algorithmen stellt diese Arbeit mehrere Ansätze zur Abschätzung der praktischen Schwierigkeit des SVP vor. Dabei verwenden wir unterschiedliche Spezial-Hardware, wie Multicore-CPUs, Grafikkarten oder "Supercomputer". Wir entwickeln parallele Algorithmen und bewerten ihre praktischen Laufzeiten. Unter anderem präsentieren wir unsere parallele Version des "Extreme Pruning Enumeration"-Algorithmus, derzeit der schnellste verfügbare SVP-Algorithmus weltweit. Unsere Implementierung hält die aktuellen Rekorde in der SVP Challenge, einem öffentlichen Wettbewerb zum Vergleich von SVP-Lösern. Unsere Arbeit beeinflusst die Sicherheit der Gitterkryptographie in zweierlei Hinsicht. Zum einen liefern wir einen Beitrag zur Beurteilung der Schwere der Worst-Case-Probleme, die die theoretische Sicherheitsgrundlage darstellt. Zum anderen zeigen wir, wie man die schnellsten praktische Angriffe auf diese Systeme im durchschnittlichen Fall verbessern kann. Als weiteres Ergebnis präsentieren wir eine Variante des "Sieving"-Algorithmus, der ebenfalls kürzeste Vektoren findet, für Idealgitter. Idealgitter sind die wichtigste Art von Gittern in der Kryptographie. Unser Algorithmus ist der Erste, der die spezielle Struktur dieser Gitter ausnutzt, so dass wir kürzeste Vektoren schneller als in regulären Gittern finden können.

Deutsch
Freie Schlagworte: Lattice-based Cryptography, Cryptanalysis, Lattice Reduction, Shortest Vector Problem
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
500 Naturwissenschaften und Mathematik > 510 Mathematik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
20 Fachbereich Informatik
Hinterlegungsdatum: 13 Dez 2011 11:38
Letzte Änderung: 05 Mär 2013 09:57
PPN:
Referenten: Buchmann, Prof. Dr. Johannes ; Cheng, Prof. Dr. Chen-Mou
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 11 November 2011
Zugehörige Links:
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen