Ace of authenticity - the versatility of digital signatures

Abstract

Digital signatures are a cornerstone of modern cryptography and a versatile building block. This thesis explores their versatility and contributes novel concepts and constructions for their use in adversarial, distributed settings. Firstly, we introduce the study of universal ring signatures (URS). Ring signatures (RS), introduced to enable whistleblowing, allow to anonymously certify that a message originates from some member of a signer group. While previous RSs rely on signers' keys to belong to compatible signature schemes, a URS works for arbitrary key combinations from any combination of potentially different signature schemes, enabling whistleblowing in uncooperative settings. Our standard model constructions rely on superpolynomial standard assumptions, witness encryption, or indistinguishability obfuscation (iO). Secondly, we introduce signature-based witness encryption, where decryption requires a threshold number of signatures from selected parties. Based on bilinear maps, we develop efficient SWE for BLS multi-signatures in the random oracle model. We integrate SWE with a blockchain to realize efficient time-release encryption without a trusted setup. Thirdly, we reduce the asymptotic complexity of SWE and present the first compact SWE with ciphertext size growing sublinearly in the number of signers. This standard model construction is based on iO and puncturable signatures.

Digitale Signaturen sind ein Eckpfeiler moderner Kryptographie und ein vielfältiger Baustein. Diese Arbeit untersucht ihre Anwendungsfelder und ergänzt neue Konzepte und Konstruktionen zur Nutzung in adversariellen, verteilten Systemen. Ein erster Beitrag ist die Studie universeller Ring-Signaturen (URS). Im Kontext von Whistleblowing wurden Ring-Signaturen (RS) eingeführt, die anonyme Attestierung einer Sendergruppen-Zugehörigkeit erlauben. Während bisherige RS Senderschlüssel kompatibler Signaturschemata erfordern, erlauben URS die Kombination beliebiger Schlüssel und ermöglichen anonymes Whistleblowing in unkooperativen Umfeldern. Unsere Standardmodell-Konstruktionen basieren auf superpolynomiellen Standardannahmen, Zeugenverschlüsselung oder Ununterscheidbarkeits-Obfuskation (iO). Zweitens führen wir signaturbasierte Zeugenverschlüsselung (SWE) ein, bei der Entschlüsselung eines Chiffrats durch eine Mindestzahl von Signaturen ausgewählter Parteien möglich wird. Auf Basis bilinearer Abbildungen entwickeln wir effizientes SWE für BLS-Multisignaturen im Zufallsorakel-Modell. Wir integrieren SWE mit einer Blockchain, um effiziente zeitbasierte Verschlüsselung ohne vertrauenswürdige Initialisierung zu realisieren. Wir reduzieren zudem die asymptotische Komplexität von SWE und stellen im Standardmodell basierend auf iO und punkturierbaren Signaturen das erste kompakte SWE-Verfahren vor, dessen Chiffratgröße sublinear in der Zahl Signierender wächst.