TU Darmstadt / ULB / TUprints

Practical Forward Secure Signatures using Minimal Security Assumptions

Hülsing, Andreas (2013)
Practical Forward Secure Signatures using Minimal Security Assumptions.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

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

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Practical Forward Secure Signatures using Minimal Security Assumptions
Language: English
Referees: Buchmann, Prof. Dr. Johannes ; Lange, Prof. Dr. Tanja
Date: 7 August 2013
Place of Publication: Darmstadt
Date of oral examination: 23 September 2013
Abstract:

Digital signatures are one of the most important cryptographic primitives in practice. They are an enabling technology for eCommerce and eGovernment applications and they are used to distribute software updates over the Internet in a secure way. In this work we introduce two new digital signature schemes: XMSS and its extension XMSS^MT. We present security proofs for both schemes in the standard model, analyze their performance, and discuss parameter selection. Both our schemes have certain properties that make them favorable compared to today's signature schemes.

Our schemes are forward secure, meaning even in case of a key compromise, previously generated signatures can be trusted. This is an important property whenever a signature has to be verifiable in the mid- or long-term. Moreover, our signature schemes are generic constructions that can be instantiated using any hash function. Thereby, if a used hash function becomes insecure for some reason, we can simply replace it by a secure one to obtain a new secure instantiation. The properties we require the hash function to provide are minimal. This implies that as long as there exists any complexity-based cryptography, there exists a secure instantiation for our schemes. In addition, our schemes are secure against quantum computer aided attacks, as long as the used hash functions are.

We analyze the performance of our schemes from a theoretical and a practical point of view. On the one hand, we show that given an efficient hash function, we can obtain an efficient instantiation for our schemes. On the other hand, we provide experimental data that show that the performance of our schemes is comparable to that of today's signature schemes. Besides, we show how to select optimal parameters for a given use case that provably reach a given level of security.

On the way of constructing XMSS and XMSS^MT, we introduce two new one-time signature schemes (OTS): WOTS+ and WOTS$. One-time signature schemes are signature schemes where a key pair may only be used once. WOTS+ is currently the most efficient hash-based OTS and WOTS$ the most efficient hash-based OTS with minimal security assumptions. One-time signature schemes have many more applications besides constructing full fledged signature schemes, including authentication in sensor networks and the construction of chosen-ciphertext secure encryption schemes. Hence, WOTS+ and WOTS$ are contributions on their own.

Altogether, this work shows the practicality and usability of forward secure signatures on the one hand and hash-based signatures on the other hand.

Alternative Abstract:
Alternative AbstractLanguage

Digitale Signaturen sind eines der meist genutzten kryptographischen Primitive in der Praxis. Sie stellen eine notwendige Technologie für eCommerce und eGovernment Anwendungen dar und werden benötigt, um Softwareupdates auf eine sichere Weise über das Internet zu verteilen. In dieser Arbeit werden zwei neue Verfahren zur digitalen Signatur vorgestellt: XMSS und dessen Erweiterung XMSS^MT. Für beide Verfahren werden Sicherheitsbeweise im Standardmodell gegeben, die Performanz analysiert und die Wahl sicherer Parameter diskutiert. Beide Verfahren haben bestimmte Eigenschaften auf Grund derer sie den heute verwendeten Verfahren zur Digitalen Signatur vorzuziehen sind.

Die vorgestellten Verfahren sind vorwärtssicher. Dies bedeutet, dass selbst im Falle einer Kompromittierung des geheimen Schlüssels, zuvor erzeugten Signaturen weiterhin vertraut werden kann. Dies ist eine wichtige Eigenschaft, die benötigt wird wenn eine Signatur über einen längeren Zeitraum verifizierbar sein muss. Darüber hinaus handelt es sich bei den vorgestellten Verfahren um generische Konstruktionen, die mit einer beliebigen kryptographischen Hashfunktion instanziiert werden können. Sollte die verwendete Hashfunktion aus irgendeinem Grund unsicher werden, reicht es aus die Hashfunktion durch eine neue, sichere Hashfunktion zu ersetzen, um eine sichere Instanziierung der Verfahren zu erhalten. Die Eigenschaften, welche wir von der verwendeten Hashfunktion fordern sind minimal. Daraus folgt, dass es eine sichere Instanziierung der vorgestellten Verfahren gibt, solange es überhaupt Komplexitäts-basierte Kryptographie gibt. Darüber hinaus bieten beide Verfahren Schutz vor Quantencomputer-basierten Angriffen, solange die verwendete Hashfunktion nicht anfällig für solche Angriffe ist.

In der vorliegenden Arbeit wird die Performanz der vorgestellten Verfahren sowohl theoretisch, als auch praktisch evaluiert. Einerseits wird gezeigt, dass eine beliebige effiziente kryptographische Hashfunktion eine effiziente Instanziierung der Verfahren ermöglicht. Andererseits werden experimentelle Ergebnisse geliefert. Diese belegen, dass die Performanz der vorgestellten Verfahren vergleichbar zu jener heute in der Praxis genutzter Verfahren ist. Weiterhin wird eine Methode vorgestellt, die es für beide Verfahren erlaubt, optimale Parameter für einen vorgegebenen Anwendungsfall zu wählen. Die erzeugten Parameter erreichen dabei beweisbar ein gegebenes Sicherheitsniveau.

Als Teil der Konstruktion von XMSS und XMSS^MT, werden zwei neue Einmalsignaturverfahren (One-Time Signature Schemes, OTS) vorgestellt: WOTS+ und WOTS$. Einmalsignaturverfahren sind Signaturverfahren, die es erlauben pro Schlüsselpaar genau eine Nachricht zu signieren. WOTS+ ist aktuell das effizienteste Hash-basierte OTS. WOTS$ ist das effizienteste OTS mit minimalen Sicherheitsannahmen. Neben der Konstruktion vollwertiger Signaturverfahren, finden OTS Verwendung in Anwendungsfällen wie der Authentifizierung in Sensornetzen oder der Konstruktion chosen-ciphertext sicherer Public-Key Verschlüsselungsverfahren. Daher stellt die Konstruktion von WOTS+ und WOTS$ einen selbständigen Beitrag dar.

Zusammenfassend belegt diese Arbeit die Praktikabilität und Nutzbarkeit vor-wärtssicherer Signaturen einerseits und Hash-basierter Signaturen andererseits.

German
URN: urn:nbn:de:tuda-tuprints-36511
Classification DDC: 000 Generalities, computers, information > 004 Computer science
500 Science and mathematics > 510 Mathematics
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
Date Deposited: 31 Oct 2013 10:39
Last Modified: 09 Jul 2020 00:32
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/3651
PPN: 333057821
Export:
Actions (login required)
View Item View Item