TU Darmstadt / ULB / tuprints

Computing Shortest Lattice Vectors on Special Hardware

Schneider, Michael :
Computing Shortest Lattice Vectors on Special Hardware.
TU Darmstadt
[Ph.D. Thesis], (2011)

[img]
Preview
PDF
Dissertation-final.pdf
Available under Creative Commons Attribution Non-commercial No Derivatives.

Download (1489Kb) | Preview
Item Type: Ph.D. Thesis
Title: Computing Shortest Lattice Vectors on Special Hardware
Language: English
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.

Alternative Abstract:
Alternative AbstractLanguage
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.German
Uncontrolled Keywords: Lattice-based Cryptography, Cryptanalysis, Lattice Reduction, Shortest Vector Problem
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
500 Naturwissenschaften und Mathematik > 510 Mathematik
Divisions: Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
Date Deposited: 13 Dec 2011 11:38
Last Modified: 07 Dec 2012 12:04
Related URLs:
URN: urn:nbn:de:tuda-tuprints-28290
License: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0
Referees: Buchmann, Prof. Dr. Johannes and Cheng, Prof. Dr. Chen-Mou
Refereed: 11 November 2011
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/2829
Export:

Actions (login required)

View Item View Item