TU Darmstadt / ULB / tuprints

On the Theory and Practice of Quantum-Immune Cryptography

Döring, Martin :
On the Theory and Practice of Quantum-Immune Cryptography.
TU Darmstadt
[Ph.D. Thesis], (2008)

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

Download (887Kb) | Preview
Item Type: Ph.D. Thesis
Title: On the Theory and Practice of Quantum-Immune Cryptography
Language: English
Abstract:

Public-key cryptography is a key technology for making the Internet and other IT infrastructures secure. The security of the established public-key cryptosystems relies on the difficulty of factoring large composite integers or computing discrete logarithms. However, it is unclear whether these computational problems remain intractable in the future. For example, Shor showed in 1994 that quantum computers can be used to factor integers and to compute discrete logarithms in polynomial time. It is therefore necessary to develop alternative public-key cryptosystems which do not rely on the difficulty of factoring or computing discrete logarithms and which are secure even against quantum computer attacks. We call such cryptosystems quantum-immune. To prove the security of these quantum-immune cryptosystems, appropriate security models have to be used. Since quantum computers are able to solve problems in polynomial time which are supposed to be intractable for classical computers, the existing security models are inadequate in the presence of quantum adversaries. Therefore, new security models have to be developed to capture quantum adversaries. Properties of these new security models have to be investigated. On a more practical level, the quantum-immune cryptosystems have to be implemented in a way that they can seamlessly replace established cryptosystems. The implementations have to be efficient and suitable for resource-constrained devices. They must easily integrate into existing public-key infrastructures. This thesis contributes to both the theory and practice of quantum-immune cryptography, addressing the above-mentioned challenges. In the theoretical part, we concentrate on the quantum zero-knowledge property of interactive proof systems. We show for the first time that the quantum statistical, perfect, and computational zero-knowledge properties are preserved under sequential composition of interactive proof systems. In the practical part, we provide implementations of the most important quantum-immune cryptosystems. We present efficiency improvements of some of the alternative cryptosystems. The implementations are very efficient and easily integrate into existing public-key infrastructures. We present comprehensive timings that show that the alternative cryptosystems are competitive or even superior compared to established cryptosystems. Finally, we present a new cryptographic API that is particularly well-suited for resource-constrained devices like mobile phones and PDAs. With this API, the alternative cryptosystems can also be used with these devices.

Alternative Abstract:
Alternative AbstractLanguage
Public-Key-Kryptografie ist eine Schlüsseltechnologie zur Absicherung des Internets und anderer IT-Infrastrukturen. Die Sicherheit etablierter Public-Key-Kryptoverfahren beruht auf der Schwierigkeit des Faktorisierens großer Zahlen oder des Berechnens diskreter Logarithmen. Es ist jedoch unklar, ob diese Probleme auch zukünftig schwer lösbar bleiben. Beispielsweise zeigte Shor 1994, dass Quanten-Computer in der Lage sind, in Polynomialzeit große Zahlen zu faktorisieren und diskrete Logarithmen zu berechnen. Deshalb müssen alternative Public-Key-Kryptoverfahren entwickelt werden, deren Sicherheit nicht auf der Schwierigkeit des Faktorisierens oder des Berechnens diskreter Logarithmen beruht, und die sicher selbst gegen Angriffe durch Quantencomputer sind. Derartige Kryptoverfahren bezeichnen wir als quanten-immun. Um die Sicherheit solcher quanten-immuner Kryptoverfahren zu beweisen, müssen geeignete Sicherheitsmodelle verwendet werden. Da Quantencomputer in der Lage sind, Probleme in Polynomialzeit zu lösen, die unlösbar (intractable) für klassische Computer sind, sind die existierenden Sicherheitsmodelle ungeeignet, die Sicherheit gegen Quanten-Angreifer zu erfassen. Daher müssen neue Sicherheitsmodelle entwickelt werden. Eigenschaften dieser neuen Sicherheitsmodelle müssen untersucht werden. Von der praktischen Ebene betrachtet, müussen die quanten-immunen Kryptoverfahren so implementiert werden, dass sie die etablierten Verfahren nahtlos ersetzen können. Die Implementierungen müssen effizient und geeignet für ressourcenbeschränkte Endgeräte sein. Sie müssen leicht in bestehende Public-Key-Infrastrukturen integriert werden können. Diese Arbeit trägt sowohl zur Theorie als auch zur Praxis von quanten-immuner Kryptografie bei. Sie adressiert dabei die oben genannten Herausforderungen. Im theoretischen Teil konzentrieren wir uns auf die Quanten-zero-knowledge-Eigenschaft interaktiver Beweissysteme. Wir zeigen erstmalig, dass die Quanten-statistical, -perfect und -computational zero-knowledge-Eigenschaften robust sind unter sequentieller Komposition interaktiver Beweissysteme. Im praktischen Teil stellen wir Implementierungen der wichtigsten quanten-immunen Kryptoverfahren vor. Für einige der Verfahren entwickeln wir Algorithmen zur Steigerung der Effizienz. Die Implementierungen sind sehr effizient und lassen sich leicht in bestehende Public-Key-Infrastrukturen integrieren. Wir präsentieren umfassende Zeitmessungen, die zeigen, dass die alternativen Kryptoverfahren vergleichbar mit etablierten Kryptoverfahren oder diesen sogar überlegen sind. Zuletzt stellen wir eine neue API für kryptografische Verfahren vor, die besonders geeignet ist für den Einsatz auf ressourcenbeschränkten Endgeräten wie Mobiltelefonen und PDAs. Mit dieser API ist es möglich, die alternativen Kryptoverfahren auch auf diesen Endgeräten einzusetzen.German
Uncontrolled Keywords: Cryptography, quantum computers, security models, implementation
Alternative keywords:
Alternative keywordsLanguage
Cryptography, quantum computers, security models, implementationEnglish
Kryptographie, Quantencomputer, Sicherheitsmodelle, ImplementierungGerman
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik
Date Deposited: 17 Oct 2008 09:23
Last Modified: 07 Dec 2012 11:54
URN: urn:nbn:de:tuda-tuprints-10729
License: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0
Referees: Buchmann, Prof. Dr. Johannes and Fischlin, Dr. Marc
Refereed: 9 July 2008
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/1072
Export:

Actions (login required)

View Item View Item