TU Darmstadt / ULB / TUbiblio

Provably Secure and Practical Signature Schemes

Coronado García, Luis Carlos (2006)
Provably Secure and Practical Signature Schemes.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (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.

Typ des Eintrags: Dissertation
Erschienen: 2006
Autor(en): Coronado García, Luis Carlos
Art des Eintrags: Erstveröffentlichung
Titel: Provably Secure and Practical Signature Schemes
Sprache: Englisch
Referenten: Buchmann, Prof. Dr. Johannes ; Petho, Prof. Dr. Attila
Berater: Buchmann, Prof. Dr. Johannes
Publikationsjahr: 26 Januar 2006
Ort: Darmstadt
Verlag: Technische Universität
Datum der mündlichen Prüfung: 13 Dezember 2005
URL / URN: urn:nbn:de:tuda-tuprints-6421
Kurzbeschreibung (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.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

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.

Deutsch
Freie Schlagworte: Merklesignaturverfahren, Multiplikationsalgorithmen, Karatsuba, Schönhage, Toom-Cook
Schlagworte:
Einzelne SchlagworteSprache
Merkle signature scheme, multiplication algorithm, karatsuba, schönhage, toom-cookEnglisch
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
Hinterlegungsdatum: 17 Okt 2008 09:22
Letzte Änderung: 22 Okt 2018 07:26
PPN:
Referenten: Buchmann, Prof. Dr. Johannes ; Petho, Prof. Dr. Attila
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 13 Dezember 2005
Schlagworte:
Einzelne SchlagworteSprache
Merkle signature scheme, multiplication algorithm, karatsuba, schönhage, toom-cookEnglisch
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen