TU Darmstadt / ULB / TUprints

On the Security of Lattice-Based Cryptography Against Lattice Reduction and Hybrid Attacks

Wunderer, Thomas (2018)
On the Security of Lattice-Based Cryptography Against Lattice Reduction and Hybrid Attacks.
Technische Universität
Ph.D. Thesis, Primary publication

[img]
Preview
Text (PDF)
Dissertation_Wunderer.pdf - Accepted Version
Copyright Information: CC BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (3MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: On the Security of Lattice-Based Cryptography Against Lattice Reduction and Hybrid Attacks
Language: English
Referees: Buchmann, Prof. Johannes ; Albrecht, Dr. Martin
Date: 2018
Place of Publication: Darmstadt
Date of oral examination: 20 September 2018
Abstract:

Over the past decade, lattice-based cryptography has emerged as one of the most promising candidates for post-quantum public-key cryptography. For most current lattice-based schemes, one can recover the secret key by solving a corresponding instance of the unique Shortest Vector Problem (uSVP), the problem of finding a shortest non-zero vector in a lattice which is unusually short. This work is concerned with the concrete hardness of the uSVP. In particular, we study the uSVP in general as well as instances of the problem with particularly small or sparse short vectors, which are used in cryptographic constructions to increase their efficiency. We study solving the uSVP in general via lattice reduction, more precisely, the Block-wise Korkine-Zolotarev (BKZ) algorithm. In order to solve an instance of the uSVP via BKZ, the applied block size, which specifies the BKZ algorithm, needs to be sufficiently large. However, a larger block size results in higher runtimes of the algorithm. It is therefore of utmost interest to determine the minimal block size that guarantees the success of solving the uSVP via BKZ. In this thesis, we provide a theoretical and experimental validation of a success condition for BKZ when solving the uSVP which can be used to determine the minimal required block size. We further study the practical implications of using so-called sparsification techniques in combination with the above approach. With respect to uSVP instances with particularly small or sparse short vectors, we investigate so-called hybrid attacks. We first adapt the “hybrid lattice reduction and meet-in-the-middle attack” (or short: the hybrid attack) by Howgrave-Graham on the NTRU encryption scheme to the uSVP. Due to this adaption, the attack can be applied to a larger class of lattice-based cryptosystems. In addition, we enhance the runtime analysis of the attack, e.g., by an explicit calculation of the involved success probabilities. As a next step, we improve the hybrid attack in two directions as described in the following. To reflect the potential of a modern attacker on classical computers, we show how to parallelize the attack. We show that our parallel version of the hybrid attack scales well within realistic parameter ranges. Our theoretical analysis is supported by practical experiments, using our implementation of the parallel hybrid attack which employs Open Multi-Processing and the Message Passing Interface. To reflect the power of a potential future attacker who has access to a large-scale quantum computer, we develop a quantum version of the hybrid attack which replaces the classical meet-in-the-middle search by a quantum search. Not only is the quantum hybrid attack faster than its classical counterpart, but also applicable to a wider range of uSVP instances (and hence to a larger number of lattice-based schemes) as it uses a quantum search which is sensitive to the distribution on the search space. Finally, we demonstrate the practical relevance of our results by using the techniques developed in this thesis to evaluate the concrete security levels of the lattice-based schemes submitted to the US National Institute of Standards and Technology’s process of standardizing post-quantum public-key cryptography.

Alternative Abstract:
Alternative AbstractLanguage

Im Laufe des letzten Jahrzehnts hat sich die gitterbasierte Kryptografie als einer der vielversprechendsten Kandidaten für post-quanten Kryptographie herauskristallisiert. Für die meisten gitterbasierten Verfahren kann der geheime Schlüssel gefunden werden, indem eine Instanz des sogenannten unique Shortest Vector Problems (uSVP), das Problem einen ungewöhnlich kurzen Vektor in einem Gitter zu finden, gelöst wird. Diese Arbeit beschäftige sich mit der Frage, wie schwer das uSVP zu lösen ist. Insbesondere studieren wir das uSVP sowohl im Allgemeinen, als auch für Instanzen, bei denen die gesuchten Vektoren besonders kurz oder dünn-besetzt sind, welche in kryptographischen Konstruktionen verwendet werden um die Effizienz zu erhöhen. Wir untersuchen das uSVP im Allgemeinen mittels Basisreduktion, genauer gesagt dem sogenannten Block-wise Korkine-Zolotarev (BKZ) Algorithmus. Um eine Instanz des uSVP mittels BKZ zu lösen, muss die Blockgröße, welche den Algorithmus spezifiziert, hinreichend groß sein. Allerdings führt eine größere Blockgröße zu einer längeren Laufzeit des Algorithmus. Deshalb ist es von großem Interesse die minimale Blockgröße zu bestimmen, welche garantiert, dass die uSVP Instanz mit BKZ erfolgreich gelöst werden kann. In dieser Arbeit präsentieren wir eine theoretische und experimentelle Validierung eines Erfolgskriteriums für BKZ um uSVP Instanzen zu lösen, welches verwendet werden kann um die minimal nötige Blockgröße zu bestimmen. Außerdem untersuchen wir die praktischen Auswirkungen sogenannter Sparsification-Techniken in Zusammenhang mit oben genanntem Ansatz. Bezüglich uSVP Instanzen mit besonders kurzen oder dünn-besetzten Vektoren untersuchen wir sogenannte Hybridangriffe. Zunächst adaptieren wir Howgrave-Grahams ``hybrid lattice reduction and meet-in-the-middle attack'' (kurz: Hybridangriff), ursprünglich entwickelt um das NTRU Verschlüsselungssystem anzugreifen, sodass damit uSVP Instanzen gelöst werden können. Dank dieser Adaption kann der Hybridangriff auf eine größere Klasse gitterbasierter kryptographischer Verfahren angewandt werden. Zusätzlich verbessern wir die Laufzeitanalyse des Angriffs, beispielsweise durch explizite Berechnungen der involvierten Erfolgswahrscheinlichkeiten. Als nächsten Schritt präsentieren wir zwei verschiedene Verbesserungen des Hybridangriffs. Um das volle Potential eines modernen Angreifers auf klassischen Computern widerzuspiegeln, parallelisieren wir den Hybridangriff. Wir zeigen, dass unsere parallele Version des Hybridangriffs für realistische Parameter gut skaliert. Unsere theoretische Analyse ist unterstützt durch praktischen Experimenten, wobei unsere Implementierung Open Multi-Processing und Message Passing Interface verwendet. Um die Mächtigkeit eines potenziellen Angreifers zu reflektieren, der Zugriff auf einen leistungsstarken Quantencomputer hat, entwickeln wir eine Quanten-Version des Hybridangriffs, welche die klassische Kollisionssuche durch eine Quanten-Suche ersetzt. Unser Quanten-Hybridangriff ist nicht nur schneller als sein klassisches Gegenstück, sondern auch noch auf einen größeren Bereich an uSVP Instanzen (und daher eine größere Anzahl an gitterbasierter Verfahren) anwendbar, da die verwendete Quanten-Suche die auf dem Suchraum zugrundeliegende Verteilung ausnutzen kann. Zum Schluss demonstrieren wir die praktische Relevanz unserer Resultate indem wir die in dieser Arbeit entwickelten Techniken verwenden, um die Sicherheitsniveaus gitterbasierter Verfahren zu bestimmen, welche zum Standardisierungsverfahren für post-quanten Kryptographie der US-amerikanischen Standardisierungsbehörde NIST eingereicht wurden.

German
URN: urn:nbn:de:tuda-tuprints-80826
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra > Cryptanalysis and Side Channel Attacks (CSCA)
20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra > Post-Quantum Cryptography
Date Deposited: 08 Oct 2018 07:54
Last Modified: 09 Jul 2020 02:22
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/8082
PPN: 437362604
Export:
Actions (login required)
View Item View Item