Secure Infrastructures in the Realm of Decentralization

Most of today's online services such as e-commerce and online banking are based on centralized service providers, hence easily prone to single points of failure, cyber-attacks and censorship. An alternative approach to mitigate this issue, is to design decentralized systems, where the control is distributed among several entities, instead of a single centralized authority. A decentralized system often consists of a complex distribution of trust among different parties, or even organizations. Henceforth, it is often challenging to build a decentralized system. It is not surprising that security guarantees of such complex decentralized systems depend on several factors: not only conventional properties of data integrity, confidentiality and authentication, but also other relevant factors such as availability, accountability and authorization. In this thesis, we aim to build provably secure infrastructures that serves a decentralized system in one way or another. Our contribution is in three different settings of blockchain, byzantine agreement and cloud.

Firstly, we consider the decentralized payment platform offered by blockchains. Although the core blockchain protocol has been thoroughly analyzed, the underling infrastructure of blockchain wallets is rather ad-hoc. Cryptocurrency wallets constitute an indispensable key management mechanism for every user that wants to send or receive blockchain payments. However, it lacks formal security analysis. We close this gap by designing provably secure wallets in presence of a classical as well as a quantum adversary. Through our security analysis, we provide concrete bit security achieved by BIP32 wallets, which is a wallet standardization deployed in many practical wallets. Interestingly, we observe that slightly modified yet equally efficient version of BIP32 achieves higher level of bit security than the original version.

Secondly, we consider the problem of byzantine agreement (BA) – a fundamental problem in distributed computing as well as an important building block in the design of decentralized systems. Classically, byzantine agreement is known to be impossible without a public key infrastructure (PKI), in presence of a corruption threshold of

Die meisten der heutigen Online-Dienste wie E-Commerce und Online-Banking basieren auf zentralisierten Dienstanbieter und sind daher leicht anfällig für einzelne Single Points of Failure, Cyberangriffe und Zensur. Ein alternativer Ansatz zur Entschärfung dieses Problems ist die Entwicklung dezentraler Systeme, bei denen die Kontrolle auf mehrere Stellen verteilt ist, anstatt auf eine einzige zentrale Behörde. Ein dezentrales System besteht oft aus einer komplexen Verteilung des Vertrauens zwischen verschiedenen Parteien oder sogar Organisationen. Daher ist es oft eine Herausforderung, ein dezentrales System aufzubauen. Es ist nicht überraschend, dass die Sicherheitsgarantien solcher komplexen dezentralen Systeme von mehreren Faktoren abhängen: nicht nur von den konventionellen Eigenschaften der Datenintegrität, Vertraulichkeit und Authentifizierung, sondern auch von anderen relevanten Faktoren wie Verfügbarkeit, Verantwortlichkeit und Autorisierung. In dieser Arbeit geht es darum, beweisbar sichere Infrastrukturen aufzubauen, die einem dezentralen System auf die eine oder andere Weise dienen. Unser Beitrag bezieht sich auf drei verschiedene Szenarien: Blockchain, „Byzantine agreement“ und Cloud. Zunächst betrachten wir die dezentralisierte Zahlungsplattform, die bieten. Obwohl das Blockchain-Kernprotokoll gründlich analysiert wurde, ist die zugrunde liegende Infrastruktur von Blockchain-Wallets eher ad-hoc. Kryptowährungs-Wallets sind ein unverzichtbarer Schlüsselverwaltungsmechanismus für jeden Nutzer, der Blockchain-Zahlungen senden oder empfangen möchte. Es fehlt jedoch an einer formalen Sicherheitsanalyse. Wir schließen diese Lücke, indem wir beweisbar sichere Wallets in Gegenwart eines klassischen und eines Quantengegners entwerfen. Durch unsere Sicherheitsanalyse liefern wir konkrete Bitsicherheit, die von BIP32-Wallets erreicht wird, einer Wallet-Standardisierung, die in vielen praktischen Wallets eingesetzt wird. Interessanterweise beobachten wir, dass eine leicht modifizierte, aber ebenso effiziente Version von BIP32 ein höheres Maß an Bitsicherheit erreicht als die Originalversion.

Zweitens betrachten wir das Problem des „Byzantine Ageement“ (BA) – ein grundlegendes Problem im verteilten Rechnen sowie ein wichtiger Baustein beim Entwurf dezentraler Systeme. Klassischerweise ist bekannt, dass BA ohne eine Public-Key-Infrastruktur (PKI) nicht möglich ist, wenn eine Korruptionsschwelle von