Enhancing the security and efficiency of distributed key generation and its applications

Abstract

Distributed Key Generation (DKG) is a fault-tolerant protocol in which n parties jointly generate a public–secret key pair. The secret key is distributed among the parties via a t-out-of-n threshold secret sharing scheme but is never reconstructed or stored in a single location. A DKG protocol is essential for bootstrapping threshold cryptosystems without relying on a trusted third party. This eliminates single points of failure and trust, which is crucial for decentralized systems such as blockchains. Key applications of DKG protocols include threshold encryption, threshold signatures, and distributed randomness generation. Indeed, many state-of-the-art Byzantine fault-tolerant (BFT) protocols employ threshold signatures and distributed randomness to enhance communication efficiency, or threshold encryption to prevent censorship. In this thesis, we make significant progress in strengthening the security guarantees and improving the efficiency of distributed key generation and its applications, particularly threshold signatures and distributed randomness generation. Our main contributions are summarized as follows: - Part I: We revisit the security of the threshold BLS signature scheme under adaptive corruptions, as used in many state-of-the-art Byzantine fault-tolerant (BFT) distributed protocols. First, we introduce a new security notion for DKG protocols and show that several existing protocols, previously proven only under static security, satisfy this notion under adaptive corruptions. Second, assuming any DKG protocol with this property, we provide a tight adaptive security proof for the threshold BLS signature scheme, thereby justifying real-world parameter choices. - Part II: We revisit the security of efficient publicly verifiable secret sharing (PVSS) schemes under adaptive corruptions, which are employed in many state-of-the-art distributed randomness beacon and DKG protocols. First, we introduce a new security notion for (aggregatable) PVSS schemes and show that several existing schemes, previously proven only under static security, satisfy it under adaptive corruptions. Second, we demonstrate that this notion directly yields adaptive security for state-of-the-art distributed randomness beacon protocols in their respective network models, which build upon (aggregatable) PVSS schemes satisfying our new notion of unpredictability. - Part III: We present a novel synchronous DKG protocol with near-quadratic communication cost, optimal corruption threshold, and adaptive security. It is the first DKG protocol in any network setting to achieve sub-cubic communication cost with an optimal corruption threshold. Furthermore, we propose a new distributed randomness beacon protocol with optimal corruption threshold, adaptive security, and quadratic communication cost per epoch in a single asynchronous round, resulting in a highly efficient randomness beacon that outperforms existing schemes. - Part IV: We introduce a novel network-agnostic DKG protocol with an optimal corruption threshold under both synchrony and asynchrony, static security, and cubic communication cost. Our construction matches the best-known DKG protocols in their respective network models. Finally, we conclude this thesis with a discussion of several open problems that may guide future research directions.

Verteilte Schlüsselerzeugung (Distributed Key Generation, DKG) ist ein fehlertolerantes Protokoll, bei dem n Parteien gemeinsam ein öffentlich–geheimes Schlüsselpaar erzeugen. Der geheime Schlüssel wird mittels eines t-aus-n-Schwellwert-Geheimnisteilungsschemas unter den Parteien verteilt, jedoch niemals rekonstruiert oder an einem einzigen Ort gespeichert. Ein DKG-Protokoll ist wesentlich für die Initialisierung (Bootstrapping) von Schwellwert-Kryptosystemen, ohne auf eine vertrauenswürdige dritte Partei angewiesen zu sein. Dadurch werden einzelne Vertrauens- und Ausfallpunkte eliminiert, was für dezentrale Systeme wie Blockchains von entscheidender Bedeutung ist. Zu den wichtigsten Anwendungen von DKG-Protokollen zählen Schwellwert-Verschlüsselung, Schwellwert-Signaturen und verteilte Zufallsgenerierung. Tatsächlich nutzen viele moderne byzantinisch fehlertolerante (BFT) Protokolle Schwellwert-Signaturen und verteilte Zufälligkeit, um die Kommunikationseffizienz zu erhöhen, oder Schwellwert-Verschlüsselung, um Zensur zu verhindern. In dieser Dissertation machen wir bedeutende Fortschritte bei der Stärkung der Sicherheitsgarantien und der Verbesserung der Effizienz der verteilten Schlüsselerzeugung und ihrer Anwendungen, insbesondere bei Schwellwert-Signaturen und der verteilten Zufallsgenerierung. Unsere wichtigsten Beiträge lassen sich wie folgt zusammenfassen: - Teil I: Wir untersuchen die Sicherheit des Schwellwert-BLS-Signaturschemas unter adaptiven Korruptionen, das in vielen modernen byzantinisch fehlertoleranten (BFT) Protokollen verwendet wird. Zunächst führen wir eine neue Sicherheitsdefinition für DKG-Protokolle ein und zeigen, dass mehrere bestehende Protokolle, die bisher nur unter statischer Sicherheit bewiesen wurden, diese Definition auch unter adaptiven Korruptionen erfüllen. Anschließend zeigen wir, unter der Annahme eines DKG-Protokolls mit dieser Eigenschaft, einen engen adaptiven Sicherheitsbeweis für das Schwellwert-BLS-Signaturschema und rechtfertigen damit die Parameterwahl in realen Anwendungen. - Teil II: Wir untersuchen die Sicherheit effizienter öffentlich verifizierbarer Geheimnisteilungsschemata (PVSS) unter adaptiven Korruptionen, die in vielen modernen Protokollen zur verteilten Zufallserzeugung und Schlüsselerzeugung eingesetzt werden. Zunächst führen wir eine neue Sicherheitsdefinition für (aggregierbare) PVSS-Schemata ein und zeigen, dass mehrere bestehende Schemata, die bisher nur unter statischer Sicherheit bewiesen wurden, diese auch unter adaptiven Korruptionen erfüllen. Anschließend zeigen wir, dass diese Definition direkt adaptive Sicherheit für moderne Protokolle zur verteilten Zufallserzeugung in ihren jeweiligen Netzwerkmodellen liefert, die auf (aggregierbaren) PVSS-Schemata beruhen, welche unsere neue Unvorhersagbarkeitsdefinition erfüllen. - Teil III: Wir präsentieren ein neuartiges synchrones DKG-Protokoll mit nahezu quadratischem Kommunikationsaufwand, optimaler Korruptionsschwelle und adaptiver Sicherheit. Es ist das erste DKG-Protokoll in allen Netzwerkmodellen, das einen subkubischen Kommunikationsaufwand bei optimaler Korruptionsschwelle erreicht. Darüber hinaus schlagen wir ein neues Protokoll für verteilte Zufallserzeugung vor, das eine optimale Korruptionsschwelle, adaptive Sicherheit und einen quadratischen Kommunikationsaufwand pro Epoche in einer einzigen asynchronen Runde aufweist, was zu einem äußerst effizienten Zufallsbeacon führt, das bestehende Verfahren übertrifft. - Teil IV: Wir stellen ein neuartiges netzwerkunabhängiges DKG-Protokoll mit optimaler Korruptionsschwelle unter sowohl synchronen als auch asynchronen Bedingungen, statischer Sicherheit und kubischem Kommunikationsaufwand vor. Unsere Konstruktion entspricht den besten derzeit bekannten DKG-Protokollen in ihren jeweiligen Netzwerkmodellen. Abschließend stellen wir einige offene Probleme vor, die als Ausgangspunkt für zukünftige Forschung dienen können.