Relax the Reliance on Honesty in Distributed Cryptographic Protocols

Distributed cryptographic protocols typically assume a bounded number of malicious parties (who behave arbitrarily) in the system---and in turn, a lower bound on the number of honest parties (who follow and only follow a protocol faithfully/honestly without performing unspecified computations)---for their respective security guarantees to hold. However, when deploying these protocols in practice, the nature of computing parties does not necessarily align nicely with the protocols' assumptions. Specifically, there may be only a few honest/compliant parties, or none exists. Instead, non-malicious parties may be semi-honest (who follow the protocol specifications but are curious to learn as much information as possible from semi-honest parties' transcripts) or rational (who take actions that maximize their utilities instead of actions benefiting the protocol the most, e.g., performing extra computations or not following protocols). In such cases, the security guarantees of such protocols may deviate greatly in real life from what is theoretically promised, leaving a huge gap between theory and practice.

In this thesis, I bridge such a gap by enhancing the fault tolerance of various distributed cryptographic primitives by relaxing the assumption on the existence of honest parties.

First, in the context of secure multi-party computations, without honest parties, my goal is to induce honest (i.e., not compromising correctness) and non-curious (i.e., not harming privacy) behaviors from rational participants via game theoretic and cryptographic techniques. In particular, I first demonstrate how to ensure protocol correctness and deter collusion among parties to recover secrets---which also breaks privacy---in multiserver private information retrieval with a singleton access structure. Then for primitives with more general (non-singleton) access structures, I introduce a distinct treatment through the lens of verifiable secret sharing. The two solutions are designed with a public bulletin board, commitment schemes, digital signature schemes, zkSNARKs (zero-knowledge succinct non-interactive arguments of knowledge), and distinct incentive structures tailored for varying access structures underlying the schemes.

Second, in permissionless blockchain systems, for protocols without privacy guarantees like computation outsourcing and consensus, my goal is to incentivize rational parties to behave correctly. This means to act according to the protocol specifications or as implied by the security requirements of the primitive, e.g., fairly distribute rewards to participants based on contributions in proof-of-work (PoW) blockchains. Specifically, I present a defense against an undercutting attack in PoW blockchains from a game theory perspective and propose a decentralized computation outsourcing protocol built on permissionless blockchain systems based on multi-unit auctions.