| Cryptographic protocols usually work under the assumption that some of the participants are perfectly honest while others are malicious adversaries. However, for many Internet-based computations it is more reasonable to assume that all or nearly all of the participants are selfishly pursuing some well-defined objective (such as making more money). Game theory studies interactions among selfish rational participants, but usually under the assumption that there is a trusted party who can organize the game and enforce the rules. This thesis presents three different examples of combining cryptographic techniques with game-theoretic analysis to produce distributed algorithms that a group of selfish rational participants would execute correctly. One example makes minimal use of a trusted party and the other two have no trusted party.; The first example is a scheme for multicast cost sharing in which there is a way for a trusted party to check whether the participants have executed the algorithm correctly and fine those who haven't. Participants maximize their payoff by executing the algorithm correctly. In the second example, two selfish players can jointly select correlated random actions without a trusted party. This is an important coordination problem. In game theory terms, the two players can achieve a correlated equilibrium without a mediator. The protocol improves on a previous solution to the same problem by being more efficient in one of the parameters (a probability distribution). The final example concerns the possibility of secret sharing when all participants are selfish and rational. We show that, under reasonable assumptions about the players' utility functions, there is no fixed-length protocol for the reconstruction of a shared secret in which selfish, rational participants will tell each other any useful information. We then provide a randomized protocol which does allow everyone to learn the reconstructed secret.; We also present history independent hash tables, which are hash tables whose memory representation reveals only their contents, and no information about the order in which elements were inserted or whether any were deleted. This is a useful method of hiding information from non-cooperating agents, so it can be used as a building block in either security applications or applications involving selfish rational agents. |
