TU Darmstadt / ULB / TUprints

High performance algorithms for lattice-based cryptanalysis

Mariano, Artur (2016)
High performance algorithms for lattice-based cryptanalysis.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
thesis.pdf
Copyright Information: In Copyright.

Download (3MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: High performance algorithms for lattice-based cryptanalysis
Language: English
Referees: Bischof, Prof. Dr. Christian ; Keshav, Prof. Dr. Pingali
Date: 22 September 2016
Place of Publication: Darmstadt
Date of oral examination: 22 September 2016
Abstract:

With quantum-computing, classical cryptosystems, such as RSA, can easily be broken. Today, lattice-based cryptography stands out as one of the most promising and prominent post-quantum type of cryptosystems. The cryptanalysis of new types of cryptography is a crucial part of their development, as it allows one to understand and improve the degree of security of these systems. The same way the security of RSA is deeply connected to the factorization of large integers, the security of lattice-based cryptography revolves around lattice problems such as the Shortest Vector Problem (SVP). While the cryptography community has developed in-depth knowledge of the algorithms that solve these problems (which we also refer to as attacks), from a theoretical point of view, the practical performance of these algorithms is commonly not well understood. In particular, the practical performance of many classes of attacks is not congruent with theoretical expectations. This gap in knowledge is problematic because the security parameters of cryptosystems are selected based on the asymptotic complexity of the available attacks, but only those that are proven to be practical and scalable are considered. Therefore, if some theoretically strong algorithms are erroneously ruled out from this process, because they are believed to be impractical or not scalable, the security parameters of cryptosystems may not be appropriate. In particular, overly strong parameters lead to inefficient cryptosystems, while overly weak parameters render cryptosystems insecure. This is the reason why one must determine the real potential of attacks in practice. The key to understanding is to consider the underlying computer architecture and its influence on the performance of these algorithms, so an effective map between the algorithm and the architecture can be done. This means in particular, to develop appropriate parallelization methods for these algorithms, as all modern computer architectures employ parallel units of various flavours. This thesis aims to fill this gap in knowledge, by describing computational analyses and techniques to parallelize and optimize attacks, with focus on sieving algorithms, in modern, parallel computer architectures. In particular, we show that (i) lattice basis reduction algorithms can benefit largely from cache friendly data structures and scale well, if the right parameters are used, (ii) enumeration algorithms can scale linearly and super-linearly if appropriate mechanisms are employed and (iii) sieving algorithms can be implemented in such a way that very good scalability is achieved, even for high core counts, if the properties of the algorithms are slightly relaxed. Throughout the thesis, we also provide heuristics to enhance the practical performance of specific algorithms, and various optimizations in practice, especially related to memory access.

Alternative Abstract:
Alternative AbstractLanguage

Vor ungefähr drei Jahrzenten hat die Kryptographiegemeinschaft begonnen gegen Angriffe mittels Quan- tencomputern resistente Kryptosysteme zu finden, aufgrund der Verletzlichkeit von klassischen Kryp- tosystemen durch diese Angriffe, wie beispielsweise RSA. Heutzutage ist die gitterbasierte Kryptographie eines der vielversprechendsten und prominentesten Post-Quantumkryptosysteme für eine Vielzahl von Gründen. Die Kryptoanalyse neuer Arten von Kryptographie ist ein wichtiger Teil ihrer Entwicklung, da es den Sicherheitsgrad dieser Systeme zu verstehen und zu verbessern ermöglicht. Auf die gleiche Weise wie die Sicherheit von RSA tief mit der Primfaktorzerlegung großer Ganzzahlen verbunden ist, dreht sich die Sicherheit der gitterbasierte Kryptographie um einige Gitterprobleme, einschließlich des “Shortest Vector Problem” (SVP). Während die Kryptographiegemeinschaft vertiefte Kenntnisse aus theoretischer Sicht der Algorithmen, die diese Probleme lösen (die wir auch als Angriffe bezeichnen), entwickelt hat, ist die praktische Perfor- manz dieser Algorithmen häufig nicht ausreichend untersucht. Insbesondere ist die praktische Leistung vieler Klassen von Angriffen nicht kongruent mit unseren theoretischen Erwartungen. Diese Wissenslücke ist problematisch, weil die Sicherheitsparameter von Kryptosystemen basierend auf der asymptotischen Komplexität der verfügbaren Angriffe ausgewählt werden, aber nur diejenigen, die praktisch und skalierbar sind, werden berücksichtigt. Wenn deshalb theoretisch starke Algotithmen fälschlicherweise aus diesem Prozess ausgeschlossen werden, sind die Sicherheitsparameter von Kryptosystemen nicht angemessen. Insbesondere führen zu starke Parameter zu ineffizienten Kryptosystemen, während übermäßig schwache Parameter Kryptosysteme unsicher machen. Dies ist der Grund, warum man das maximale Potenzial aller Angriffe in der Praxis bestimmen muss. Der Schlüssel um das maximale Potenzial zu erreichen, ist (i) die darunterliegende Computerarchitektur und deren Einfluss auf die Leistung dieser Algorithmen zu betrachten, so dass eine effektive Abbildung zwischen dem Algorithmus und der Architektur durchgeführt werden kann, und (ii) die Entwicklung geeigneter Parallelisierungsmethoden für diese Algorithmen, da moderne Computerarchitekturen überwiegend parallel sind. Diese Arbeit zielt darauf ab diese Wissenslücke zu füllen mittels der Beschreibungen von rechnerischen Analysen und Parallelisierungs- und Optimierungstechniken von Angriffen, mit Fokus auf “Sieving” Algorithmen, in modernen, parallelen Rechnerarchitekturen. Insbesondere zeigen wir, dass (i) Gitterbasis Reduktionsalgorithmen weitgehend von “Cache”-freundlichen Datenstrukturen profitieren können und dass sie gut skalieren, wenn die richtigen Parameter verwendet werden, (ii) “Enumeration” Algorithmen können linear und super-linear skalieren, wenn geeignete Mechanismen eingesetzt werden und (iii) “Sieving” Algorithmen können in einer Weise implementiert werden, die sehr gute Skalierbarkeit erreicht, selbst für ein hohe Anzahl von Kernen, wenn die Eigenschaften der Algorithmen leicht entspannt und ausgenutzt werden. Im Lauf der These beschreiben wir auch Heuristiken, um die praktische Leistung von spezifischen Algorithmen zu verbessern, und verschiedenen praktischen Optimierungen, vor allem Verbesserungen im Zusammenhang mit dem Speicherzugriff.

German
URN: urn:nbn:de:tuda-tuprints-57523
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Algorithmics
20 Department of Computer Science > Cryptography and Complexity Theory
20 Department of Computer Science > Parallel Programming
Date Deposited: 17 Nov 2016 15:42
Last Modified: 17 Nov 2016 15:42
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/5752
PPN: 395921635
Export:
Actions (login required)
View Item View Item