TU Darmstadt / ULB / TUprints

On the Security of Lattice-Based Signature Schemes in a Post-Quantum World

Bindel, Nina (2018)
On the Security of Lattice-Based Signature Schemes in a Post-Quantum World.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PhD thesis of Nina Bindel - Text
Dissertation_NBindel_v1.pdf - Published Version
Copyright Information: CC BY-NC-ND 4.0 International - Creative Commons, Attribution NonCommercial, NoDerivs.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: On the Security of Lattice-Based Signature Schemes in a Post-Quantum World
Language: English
Referees: Buchmann, Prof. Dr. Johannes ; Stebila, Prof. Dr. Douglas
Date: 2018
Place of Publication: Darmstadt
Date of oral examination: 20 September 2018
Abstract:

Digital signatures are indispensable for security on the Internet, because they guarantee authenticity, integrity, and non-repudiation, of namely e-mails, software updates, and in the Transport Layer Security (TLS) protocol which is used for secure data transfer, for example. Most signature schemes that are currently in use such as the RSA signature scheme, are considered secure as long as the integer factorization problem or the discrete logarithm (DL) problem are computationally hard. At present, no algorithms have yet been found to solve these problems on conventional computers in polynomial time. However, in 1997, Shor published a polynomial-time algorithm that uses quantum computation to solve the integer factorization and the DL problem. In particular, this means that RSA signatures are considered broken as soon as large-scale quantum computers exist. Due to significant advances in the area of quantum computing, it is reasonable to assume that within 20 years, quantum computers that are able to break the RSA scheme, could exist. In order to maintain authenticity, integrity, and non-repudiation of data, cryptographic schemes that cannot be broken by quantum attacks are required. In addition, these so-called post-quantum secure schemes should be sufficiently efficient to be suitable for all established applications. Furthermore, solutions enabling a timely and secure transition from classical to post-quantum schemes are needed. This thesis contributes to the above-mentioned transition. In this thesis, we present the two lattice-based digital signature schemes TESLA and qTESLA, whereby lattice-based cryptography is one of five approaches to construct post-quantum secure schemes. Furthermore, we prove that our signature schemes are secure as long as the so-called Learning With Errors (LWE) problem is computationally hard to solve. It is presumed that even quantum computers cannot solve the LWE problem in polynomial time. The security of our schemes is proven using security reductions. Since our reductions are tight and explicit, efficient instantiations are possible that provably guarantee a selected security level, as long as the corresponding LWE instance provides a certain hardness level. Since both our reductions (as proven in the quantum random oracle model) and instantiations, take into account quantum attackers, TESLA and qTESLA are considered post-quantum secure. Concurrently, the run-times for generating and verifying signatures of qTESLA are similar (or faster) than those of the RSA scheme. However, key and signature sizes of RSA are smaller than those of qTESLA. In order to protect both the theoretical signature schemes and their implementations against attacks, we analyze possible vulnerabilities against implementation attacks. In particular, cache-side-channel attacks resulting from observing the cache behavior and fault attacks, which recover secret information by actively disrupting the execution of an algorithm are focused. We present effective countermeasures for each implementation attack we found. Our analyses and countermeasures also influence the design and implementation of qTESLA. Although our schemes are considered (post-quantum) secure according to state-of-the-art LWE attacks, cryptanalysis of lattice-based schemes is still a relatively new field of research in comparison to RSA schemes. Hence, there is a lack of confidence in the concrete instantiations and their promised security levels. However, due to developments within the field of quantum computers, a transition to post-quantum secure solutions seems to be more urgently required than ever. To solve this dilemma, we present an approach to combine two schemes, e.g., qTESLA and the RSA signature scheme, so that the combination is secure as long as one of the two combined schemes is secure. We present several of such combiners to construct hybrid signature schemes and hybrid key encapsulation mechanisms to ensure both authenticity and confidentiality in our Public-Key Infrastructure (PKI). Lastly, we also demonstrate how to apply the resulting hybrid schemes in standards such as X.509 or TLS. To summarize, this work presents post-quantum secure candidates which can, using our hybrid schemes, add post-quantum security to the current classical security in our PKI.

Alternative Abstract:
Alternative AbstractLanguage

Digitale Signaturen sind für die Sicherheit im Internet unabdingbar, denn sie garantieren Authentizität, Integrität und Nachweisbarkeit, beispielsweise von E-Mails, von Software-Updates, oder im Transport Layer Security (TLS) Protokoll welches für sichere Datenübertragung genutzt wird. Die meisten zur Zeit genutzten Signaturverfahren, wie zum Beispiel das RSA-Signaturverfahren, gelten als sicher solang das Primzahlfaktorisierungs-Problem oder das Diskreter-Logarithmus-Problem (DL-Problem) schwer ist. Bis heute wurden keine Algorithmen gefunden, welche diese Probleme auf herkömmlichen Rechnern in polynomieller Zeit lösen. Allerdings veröffentlichte Shor 1997 einen Algorithmus, welcher unter Nutzung von Quantenberechnungen das Primzahlfaktorisierungs- und das DL-Problem in polynomieller Zeit löst. Das bedeutet insbesondere, dass das RSA-Signaturverfahren gebrochen werden kann, sobald entsprechend mächtige Quantencomputer existieren. Aufgrund der bedeutenden technischen Fortschritte im Bereich der Quantenforschung erscheint es möglich, dass in bereits 20 Jahren Quantcomputer existieren werden, welche in der Lage sein werden das RSA-Verfahren zu brechen. Um Authentizität, Integrität und Nachweisbarkeit von Daten auch weiterhin zu garantieren, werden Verfahren benötigt, welche nicht durch Quantenangriffe gebrochen werden können. Außerdem sollten diese Post-Quanten-Verfahren effizient genug sein, um weiterhin in den etablierten Anwendungsfällen einsetzbar zu sein. Zusätzlich sind Lösungen gefragt, welche eine zeitnahe und sichere Umstellung von klassischen auf Post-Quanten-Verfahren ermöglichen. Die vorliegende Arbeit trägt zu dieser angestrebten Umstellung bei. In dieser Arbeit stellen wir die beiden gitterbasierte Signaturverfahren TESLA und qTESLA vor, wobei gitterbasierte Kryptograpfie einer von fünf möglichen Ansätzen zur Konstruktion von Post-Quanten-Verfahren ist. Des Weiteren beweisen wir, dass unsere beiden Verfahren sicher sind, solang das sogenannte Learning-With-Errors-Problem (LWE-Problem) schwer zu lösen ist. Derzeit wird angenommen, dass selbst Quantencomputer das LWE-Problem nicht in polynomieller Zeit lösen können. Wir beweisen die Sicherheit unserer Verfahren mit Hilfe einer Sicherheitsreduktion. Da unsere Reduktion die Eigenschaften strikt und explizit erfüllt, sind effiziente Instanziierungen möglich, welche beweisbar ein gewähltes Sicherheitslevel garantieren, solang die korrespondierende LWE-Instanz ein bestimmtes Schwierigkeitslevel hat. Sowohl unsere Reduktion (welche im Quantum-Random-Oracle Modell bewiesen wurde) als auch unsere Instanziierung Quantenangreifer berücksichtigt, gelten TESLA und qTESLA als post-quanten-sicher. Gleichzeitig entsprechen die Laufzeiten der Signaturgenerierung und -verifikation von qTESLA denen des RSA-Verfahrens. Allerdings sind die Schlüssel- und Signaturgrößen von RSA kleiner als die von qTESLA. Um nicht nur die theoretischen Signaturverfahren, sondern auch deren Implementierungen gegen Angriffe zu schützen, analysieren wir mögliche Schwachstellen bezüglich Implementierungsangriffen. Besonderes Augenmerk liegt dabei zum einen auf Cache-Seitenkanalangriffen, welche durch die Beobachtung des Cache-Verhaltens entstehen, und zum anderen auf Fehlerangriffen, welche geheime Informationen über das aktive Stören des Programmablaufs gewinnen. Zu jedem von uns gefundenen Implementierungsangriff stellen wir effektive Gegenmaßnahmen vor. Unsere Analysen und Gegenmaßnahmen beeinflussen auch das Design und die Implementierung von qTESLA. Wenngleich unsere Verfahren nach heutigem Stand als (post-quanten-)sicher gelten, so ist die Kryptoanalyse gitterbasierter Verfahren ein relativ neues Forschungsfeld im Vergleich etwa zum RSA-Signaturverfahren. Entsprechend fehlt es an Vertrauen in die Instanziierungen und deren versprochener Sicherheitslevel. Aufgrund der Entwicklungen bezüglich Quantencomputern, erscheint jedoch gleichzeitig eine Umstellung auf post-quanten-sichere Verfahren drängender denn je. Um dieses Dilemma zu lösen, stellen wir in dieser Arbeit eine Methode vor, um zwei Verfahren, beispielsweise qTESLA und das RSA-Signaturverfahren, so zu kombinieren, dass die Sicherheit der Kombination gewahrt ist, solang eines der beiden kombinierten Verfahren sicher ist. Wir präsentieren verschiedene solcher sogenannten Hybrid-Kombinierer für Signaturverfahren und Key-Encapsulation-Mechanismen, um sowohl Authentiziät als auch Vertraulichkeit in unserer Public-Key Infrastruktur (PKI) zu garantieren. Abschließend demonstrieren wir die Anwendung der resultierenden Hybrid-Verfahren in Standards wie dem Zertifikatsstandard X.509 oder TLS. Zusammengefasst präsentiert diese Arbeit also post-quanten-sichere Kandidaten welche mit Hilfe von vorgestellten Hybrid-Verfahren die klassiche Sicherheit unserer PKI um Post-Quanten-Sicherheit erweitern.

German
URN: urn:nbn:de:tuda-tuprints-81009
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 > Post-Quantum Cryptography
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1119: CROSSING – Cryptography-Based Security Solutions: Enabling Trust in New and Next Generation Computing Environments
Date Deposited: 24 Oct 2018 12:01
Last Modified: 09 Jul 2020 02:22
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/8100
PPN: 437892123
Export:
Actions (login required)
View Item View Item