TU Darmstadt / ULB / TUprints

Post-quantum signatures for today

Dahmen, Erik (2009)
Post-quantum signatures for today.
Technische Universität
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
dissertation.dahmen.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (627kB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Post-quantum signatures for today
Language: English
Referees: Buchmann, Prof. Dr. Johannes ; Ding, Prof. Dr. Jintai
Date: 9 February 2009
Place of Publication: Darmstadt
Date of oral examination: 5 February 2009
Corresponding Links:
Abstract:

Digital signatures are essential for the security of computer networks such as the Internet. For example, digital signatures are widely used to ensure the authenticity and integrity of updates for operating systems and other software applications. The security of the few practically used signature schemes is threatened by quantum computers. When large quantum computers are built, all currently used signature schemes will become insecure. It is therefore of extreme importance to develop alternative signature schemes that remain secure in the presence of quantum computers and which are able to compete with currently used signature schemes. A very promising candidate for a signature scheme that withstands quantum computer attacks is the Merkle signature scheme invented by Merkle in 1979. However, even combined with the improvements by Szydlo and Coronado, the Merkle signature scheme has certain efficiency drawbacks that keep it from being truly practical. First of all, it has highly unbalanced signature generation times. In the worst case, signature generation takes significantly longer than on average. Secondly, the Merkle--Szydlo--Coronado signature scheme produces very large signatures. It is also unclear if Merkle's signature scheme is suitable for application on resource constrained devices. The generalized Merkle signature scheme (GMSS) presented in this thesis solves the problems mentioned above. It drastically reduces the worst case signature generation time of the Merkle--Szydlo--Coronado signature scheme. The worst case signature generation time of GMSS corresponds to the average case signature generation time of the Merkle--Szydlo--Coronado signature scheme. Further, the worst case signature generation time of GMSS is extremely close to its average case signature generation time and thus, GMSS provides balanced timings for the signature generation. GMSS exploits the improved signature generation times to provide a noticeable reduction of the signature sizes while maintaining timings that are highly competitive to currently used signature schemes. A proof-of-concept implementation shows that GMSS can also be used on resource constrained devices and excellently compares to currently used signature schemes. This thesis also introduces a new construction method for Merkle signatures. This construction is provably secure under weaker security assumptions and yields a signature scheme with a significantly higher security level compared to the original construction.

Alternative Abstract:
Alternative AbstractLanguage

Digitale Signaturen sind von wesentlicher Bedeutung für die Sicherheit von Computernetzwerken wie dem Internet. Digitale Signaturen werden zum Beispiel eingesetzt, um die Authentizität und Integrität von Updates für Betriebssysteme und andere Software-Anwendungen zu gewährleisten. Die Sicherheit der wenigen in der Praxis eingesetzen Signaturverfahren ist durch Quantencomputer bedroht. Alle derzeit verwendeten Signaturverfahren werden unsicher, sobald große Quantencomputer gebaut werden können. Die Erforschung von alternativen Signaturverfahren, welche Angriffen durch Quantencomputer standhalten und konkurrenzfähig zu den heute verwendeten Verfahren sind, ist daher von sehr großer Bedeutung. Ein viel versprechender Kandidat für ein Signaturverfahren, dass sicher gegen Angriffe durch Quantencomputer ist, ist das im Jahre 1979 von Merkle erfundene Merkle-Signaturverfahren. Allerdings hatte das Merkle-Signaturverfahren, selbst in Kombination mit den Verbesserungen von Szydlo und Coronado Effizienzprobleme, die es davon abgehalten haben wirklich praktisch zu sein. Zunächst einmal sind die Signierzeiten sehr unbalanciert. Signieren dauert im Worst-Case wesentlich länger als im Average-Case. Weiter produziert das Merkle-Szydlo-Coronado-Signaturverfahren sehr große Signaturen. Ebenfalls ist unklar ob Merkles Signaturverfahren in ressourcenbeschränkten Geräten einsetzbar ist. Diese Arbeit präsentiert das "generalized Merkle signature scheme" (GMSS), ein Signaturverfahren, welches die oben genannten Probleme löst. GMSS hat eine signifikant bessere Worst-Case-Signierzeit als das Merkle-Szydlo-Coronado-Signaturverfahren. Die Worst-Case-Signierzeit von GMSS entspricht der Average-Case-Signierzeit des Merkle-Szydlo-Coronado-Signaturverfahrens. Weiter ist die Worst-Case-Signierzeit von GMSS sehr nah an seiner Average-Case-Signierzeit. Damit stellt GMSS balancierte Zeiten für die Signaturerzeugung zur Verfügung. GMSS nutzt die verbesserten Signierzeiten, um die Größe der Signaturen spürbar zu verringern und bewahrt dabei Zeiten, die konkurrenzfähig zu den heute verwendeten Signaturverfahren sind. Eine Implementierung auf einem Microcontroller zeigt, dass GMSS auch in ressourcenbeschränkten Geräten einsetzbar ist. Diese Arbeit beschreibt weiterhin eine neue Konstruktionsmethode für Merkle Signaturen. Die neue Konstruktion ist beweisbar sicher unter schwächeren Sicherheitsannahmen und liefert ein Signaturverfahren mit signifikant höherem Sicherheitsniveau im Vergleich zu der ursprünglichen Konstruktion.

German
URN: urn:nbn:de:tuda-tuprints-13196
Classification DDC: 000 Generalities, computers, information > 004 Computer science
500 Science and mathematics > 510 Mathematics
Divisions: 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
Date Deposited: 27 Feb 2009 12:47
Last Modified: 08 Jul 2020 23:17
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/1319
PPN: 209663065
Export:
Actions (login required)
View Item View Item