TU Darmstadt / ULB / tuprints

Provably Secure and Practical Signature Schemes

Coronado García, Luis Carlos :
Provably Secure and Practical Signature Schemes.
[Online-Edition]
TU Darmstadt
[Ph.D. Thesis], (2006)

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

Download (3069Kb) | Preview
Item Type: Ph.D. Thesis
Title: Provably Secure and Practical Signature Schemes
Language: English
Abstract:

This work contributes to two independent topics: (1) Provably secure and efficient signature schemes and (2) the analysis of certain integer multiplication algorithms. It is uncertain whether quantum computers are feasible that are powerful enough to solve non-trivial problems. In 1994, Shor proposed a quantum algorithm for solving both the integer factorization problem and the discrete logarithm problem in polynomial time. This algorithm clearly renders signature schemes like RSA, DSA or ElGamal completely insecure as soon as powerful quantum computers come into existence. In this thesis we propose signature schemes that are provably secure and efficient. The security of the described schemes relies on the security of hash function and the pseudorandom bit generator used. We also study and compare certain integer multiplication algorithms. The motivation of this comparison is the use of modular exponentiation -- which, in turn, needs the multiplication of large integers -- in often used signature schemes like RSA, DSA, and ElGamal. Our study is more detailed than just the asymptotic behaviour, since we take multiplication and addition of base-words into account.

Alternative Abstract:
Alternative AbstractLanguage
Diese Arbeit leistet Beiträge zu zwei unabhängige Themen: (1) Beweisbar sichere und effiziente Signaturverfahren und (2) die Analyse von Algorithmen zur Multiplikation ganzer Zahlen. Es ist nach wie vor ungewiss, ob Quantenrechner gebaut werden können, die groß genug sind, um kryptographisch relevante Probleme zu lösen. Shor stellte 1994 einen Quantenalgorithmus vor, der das Faktorisierungsproblem für ganze Zahlen und das Diskrete-Logarithmen-Problem mit polynomiellen Aufwand löst. Signaturverfahren wie RSA, DSA und ElGamal werden mit der Verfügbarkeit von Quantenrechnern offensichtlich unsicher. Immerhin berichten Breyta et al. von einer erfolgreichen Implementierung dieses Algorithmus auf einem Quantenregister bestehend aus siben Qubits. In der vorgelegten Arbeit schlagen wir Signaturverfahren vor, die beweisbar sicher und effizient sind. Die Sicherheit der beschreibenen Verfahren basiert auf der Sicherheit der eingesetzten Hashfunktion und des pseudozufälligen Bitgenerators. Ferner untersuchen und vergleichen wir einige Multiplikationsmethoden. Dieser Vergleich wurde dadurch motiviert, dass einige der am weitesten verbreiteten Signaturverfahren -- RSA, DSA und ElGamal -- die modularen Exponentiation verwenden, was eine schnelle Multiplikation großer ganzer Zahlen erfordert. Unsere Untersuchung geht über das einfache asymptotische Verhalten der Verfahren hinaus, weil wir die Multiplikationen und Additionen der zu Grunde liegenden Maschinentypen einbeziehen.German
Uncontrolled Keywords: Merklesignaturverfahren, Multiplikationsalgorithmen, Karatsuba, Schönhage, Toom-Cook
Alternative keywords:
Alternative keywordsLanguage
Merklesignaturverfahren, Multiplikationsalgorithmen, Karatsuba, Schönhage, Toom-CookGerman
Merkle signature scheme, multiplication algorithm, karatsuba, schönhage, toom-cookEnglish
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik
Date Deposited: 17 Oct 2008 09:22
Last Modified: 10 Dec 2012 10:06
Official URL: http://elib.tu-darmstadt.de/diss/000642
URN: urn:nbn:de:tuda-tuprints-6421
License: Simple publication rights for ULB
Referees: Buchmann, Prof. Dr. Johannes and Petho, Prof. Dr. Attila
Advisors: Buchmann, Prof. Dr. Johannes
Refereed: 13 December 2005
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/642
Export:

Actions (login required)

View Item View Item