Improvements and New Constructions of Digital Signatures

Ein digitales Signaturverfahren, oft auch nur digitale Signatur genannt, ist ein wichtiger und nicht mehr wegzudenkender Baustein in der Kryptographie.
Es stellt das digitale Äquivalent zur klassischen handschriftlichen Signatur dar und liefert darüber hinaus noch weitere wünschenswerte Eigenschaften.

Mit solch einem Verfahren kann man einen öffentlichen und einen geheimen Schlüssel erzeugen. Der geheime Schlüssel dient zur Erstellung von Signaturen zu beliebigen Nachrichten. Diese können mit Hilfe des öffentlichen Schlüssels von jedem überprüft und somit verifiziert werden. ... mehr

Desweiteren fordert man, dass das Verfahren "sicher" sein soll. Dazu gibt es in der Literatur viele verschiedene Begriffe und Definitionen, je nachdem welche konkreten Vorstellungen beziehungsweise Anwendungsgebiete man hat.
Vereinfacht gesagt, sollte es für einen Angreifer ohne Kenntnis des geheimen Schlüssels nicht möglich sein eine gültige Signatur zu einer beliebigen Nachricht zu fälschen.
Ein sicheres Signaturverfahren kann somit verwendet werden um die folgenden Ziele zu realisieren:

- Authentizität: Jeder Empfänger kann überprüfen, ob die Nachricht von einem bestimmten Absender kommt.
- Integrität der Nachricht: Jeder Empfänger kann feststellen, ob die Nachricht bei der Übertragung verändert wurde.
- Nicht-Abstreitbarkeit: Der Absender kann nicht abstreiten die Signatur erstellt zu haben.

Damit ist der Einsatz von digitalen Signaturen für viele Anwendungen in der Praxis sehr wichtig. Überall da, wo es wichtig ist die Authentizität und Integrität einer Nachricht sicherzustellen, wie beim elektronischen Zahlungsverkehr, Softwareupdates oder digitalen Zertifikaten im Internet, kommen digitale Signaturen zum Einsatz.

Aber auch für die kryptographische Theorie sind digitale Signaturen ein unverzichtbares Hilfsmittel. Sie ermöglichen zum Beispiel die Konstruktion von stark sicheren Verschlüsselungsverfahren.

Eigener Beitrag: Wie bereits erwähnt gibt es unterschiedliche Sicherheitsbegriffe im Rahmen von digitalen Signaturen. Ein Standardbegriff von Sicherheit, der eine recht starke Form von Sicherheit beschreibt, wird in dieser Arbeit näher betrachtet. Die Konstruktion von Verfahren, die diese Form der Sicherheit erfüllen, ist ein vielschichtiges Forschungsthema. Dazu existieren unterschiedliche Strategien in unterschiedlichen Modellen. In dieser Arbeit konzentrieren wir uns daher auf folgende Punkte.

- Ausgehend von vergleichsweise realistischen Annahmen konstruieren wir ein stark sicheres Signaturverfahren im sogenannten Standardmodell, welches das realistischste Modell für Sicherheitsbeweise darstellt. Unser Verfahren ist das bis dahin effizienteste Verfahren in seiner Kategorie. Es erstellt sehr kurze Signaturen und verwendet kurze Schlüssel, beides unverzichtbar für die Praxis.

- Wir verbessern die Qualität eines Sicherheitsbeweises von einem verwandten Baustein, der identitätsbasierten Verschlüsselung. Dies hat unter anderem Auswirkung auf dessen Effizienz bezüglich der empfohlenen Schlüssellängen für den sicheren Einsatz in der Praxis. Da jedes identitätsbasierte Verschlüsselungsverfahren generisch in ein digitales Signaturverfahren umgewandelt werden kann ist dies auch im Kontext digitaler Signaturen interessant.


- Wir betrachten Varianten von digitalen Signaturen mit zusätzlichen Eigenschaften, sogenannte aggregierbare Signaturverfahren. Diese ermöglichen es mehrere Signaturen effizient zu einer zusammenzufassen und dabei trotzdem alle zugehörigen verschiedenen Nachrichten zu verifizieren. Wir geben eine neue Konstruktion von solch einem aggregierbaren Signaturverfahren an, bei der das Verfahren eine Liste aller korrekt signierten Nachrichten in einer aggregierten Signatur ausgibt anstatt, wie bisher üblich, nur gültig oder ungültig. Wenn eine aggregierte Signatur aus vielen Einzelsignaturen besteht wird somit das erneute Berechnen und eventuell erneute Senden hinfällig und dadurch der Aufwand erheblich reduziert.

A digital signature scheme, or short digital signature, is an important and indispensable cryptographic building block. It is the digital equivalent of the classical handwritten signature and provides even more desirable features.

A digital signature scheme generates a public key and a secret key. The secret key is used to create signatures for arbitrary messages. This can be publicly verified by anyone who is aware of the public key.

Furthermore one requires that the scheme should be ``secure''. There are many different terms and definitions in the literature, depending on the application. ... mehrInformally, it should not be possible for an adversary to forge a valid signature of an arbitrary message without knowing the secret key.
A secure digital signature scheme can therefore be used to achieve the following security goals:

- Authentication: Each receiver can verify whether the message comes from a specific sender.
- Data Integrity: Each receiver can determine whether the message was modified during transmission.
- Non-Repudiation: The sender cannot deny having created the signature.
Thus the use of digital signatures is very important for many applications in practice. Wherever it is important to ensure the authenticity and integrity of a message, such as in electronic payment transactions, software updates or digital certificates on the Internet, digital signatures are used.

Digital signatures are also a very important tool for cryptographic theory. For example, they enable the construction of strongly secure encryption schemes.

Own Contribution: As already mentioned, there are different security notions in the context of digital signatures. A standard notion of security, which describes a rather strong form of security, is examined in detail in this work. The construction of digital signature schemes that fulfill this form of security is a rich research topic. Different strategies exist in different models. In this thesis we therefore focus on the following points.

- Based on comparatively realistic assumptions, we construct a strongly secure digital signature scheme in the so-called standard model, which is the most realistic model for security proofs. Our scheme was the most efficient digital signature scheme in its category at that time. The scheme creates very short signatures and uses short keys, both essential for practical use.

- We improve the quality of a security proof of a related building block, called identity-based encryption, which allow us, e.g., to reduce the recommended key length for secure use in practice. Any identity-based encryption scheme can be generically transformed into a digital signature scheme. Thus our improvements are also interesting regarding digital signatures.

- We consider variants of digital signatures with additional features, so-called aggregate signature schemes. These allow to efficiently combine several signatures into one and still verify all associated messages. We improve verification of aggregate signatures by constructing a new scheme, where the verification algorithm outputs a list of all correctly signed messages in an aggregate signature instead of only valid or invalid. If an aggregated signature consists of many individual signatures, re-computations and possibly re-sending of all individual signatures becomes obsolete, which reduces a lot of costs.