TU Darmstadt / ULB / TUbiblio

On the Theory and Practice of Quantum-Immune Cryptography

Döring, Martin (2008):
On the Theory and Practice of Quantum-Immune Cryptography.
Darmstadt, Technische Universität, TU Darmstadt, [Online-Edition: urn:nbn:de:tuda-tuprints-10729],
[Ph.D. Thesis]

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.

Item Type: Ph.D. Thesis
Erschienen: 2008
Creators: Döring, Martin
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.

Place of Publication: Darmstadt
Publisher: Technische Universität
Uncontrolled Keywords: Cryptography, quantum computers, security models, implementation
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
Date Deposited: 17 Oct 2008 09:23
Official URL: 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 / Verteidigung / mdl. Prüfung: 9 July 2008
Alternative keywords:
Alternative keywordsLanguage
Kryptographie, Quantencomputer, Sicherheitsmodelle, ImplementierungGerman
Alternative Abstract:
Alternative abstract Language
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
Export:
Suche nach Titel in: TUfind oder in Google

Optionen (nur für Redakteure)

View Item View Item