Security and privacy of incentive-driven mechanisms

While cryptographic tools offer practical security and privacy supported by theory and formal proofs, there are often gaps between the theory and intricacies of the real world. This is especially apparent in the realm of game theoretic applications where protocol participants are motivated by incentives and preferences on the protocol outcome. These incentives can lead to additional requirements or unexpected attack vectors, making standard cryptographic concepts inapplicable. The goal of this thesis is to bridge some of the gaps between cryptography and incentive-driven mechanisms. The thesis will consist of three main research threads, each studying the privacy or security of a game-theoretic scenario in non-standard cryptographic frameworks in order to satisfy the scenario’s unique requirements. Our first scenario is preference aggregation, where we will analyze the privacy of voting rules while requiring the rules to be deterministic. Then, we will study games, and how to achieve collusion-freeness (and its composable version, collusion-preservation) in the decentralized setting. Finally, we explore the robustness of Nakamoto-style proof-of-work blockchains against 51% attacks when the main security assumption of honest majority fails. Most of the results in this thesis are also published in the following (in order): Ch. 3: [103], Ch. 4: [47], and Ch. 5: [104]. Our first focus is preference aggregation—in particular voting rules. Specifically, we answer the crucial question: How private is the voting rule we use and the voting information we release? This natural and seemingly simple question was sidestepped in previous works, where randomization was added to voting rules in order to achieve the widely-known notion of differential privacy (DP). Yet, randomness in an election can be undesirable, and may alter voter incentives and strategies. In this chapter of our thesis, we expand and improve upon previous works and study deterministic voting rules. In a similarly well-accepted framework of distributional differential privacy (DDP), we develop new techniques in analyzing and comparing the privacy of voting rules—leading to a new measure to contrast different rules in addition to existing ones in the field of social choice. We learn the positive message that even vote tallies have very limited privacy leakage that decreases quickly in the number of votes, and a surprising fact that outputting the winner using different voting rules can result in asymptotically different privacy leakage. Having studied privacy in the context of parties with preferences and incentives, we turn our attention to the secure implementation of games. Specifically, we study the issue of collusion and how to avoid it. Collusion, or subliminal communication, can introduce undesirable coalitions in games that allow malicious parties, e.g. cheating poker players, a wider set of strategies. Standard cryptographic security is insufficient to address the issue, spurring on a line of work that defined and constructed collusion-free (CF), or its composable version, collusion-preserving (CP) protocols. Unfortunately, they all required strong assumptions on the communication medium, such as physical presence of the parties, or a restrictive star-topology network with a trusted mediator in the center. In fact, CF is impossible without restricted communication, and CP is conjectured to always require a mediator. Thus, circumventing these impossibilities is necessary to truly implement games in a decentralized setting. Fortunately, in the rational setting, the attacker can also be assumed to have utility. By ensuring collusion is only possible by sending incorrect, penalizable messages, and composing our protocol with a blockchain protocol as the source of the penalization, we prove our protocol as CP against incentive-driven attackers in a framework of rational cryptography called rational protocol design (RPD). Lastly, it is also useful to analyze the security of the blockchain and its associated cryptocurrencies—cryptographic transaction ledger protocols with embedded monetary value— using a rational cryptography framework like RPD. Our last chapter studies the incentives of attackers that perform 51% attacks by breaking the main security assumption of honest majority in proof-of-work (PoW) blockchains such as Bitcoin and Ethereum Classic. Previous works abstracted the blockchain protocol and the attacker’s actions, analyzing 51% attacks via various techniques in economics or probability theory. This leads open the question of exploring this attack in a model closer to standard cryptographic analyses. We answer this question by working in the RPD framework. Improving upon previous analyses that geared towards only mining rewards, we construct utility functions that model the incentives of 51% attackers. Under the RPD framework, we are able to determine when an attacker is incentivized to attack a given instantiation of the blockchain protocol. More importantly, we can make general statements that indicate changes to protocol parameters to make it secure against all rational attackers under these incentives