|Abstract as per original application
This project will investigate distributed protocols that securely realize mechanisms for various allocation and selection problems among self-serving agents. In blockchain applications, an assignment protocol enables fair distribution of goods or chores among agents without any trusted central authority, and a selection protocol lets investors with conflicting interests decide which combination of crowdfunding projects to sponsor.
In the literature, deterministic notions of fairness have been considered, but sometimes randomness is necessary. For instance, in the lottery problem, which is a special case of both assignment and selection problems, one prize is given to exactly one agent. The only reasonable mechanism is to select one agent uniformly at random as the winner. However, without a trusted authority, the agents themselves are responsible for generating the randomness in a distributed protocol. Unfortunately, standard cryptographic approaches such as secure multi-party computation require a majority of the agents to be honest, which is not a realistic assumption, because every agent might deviate from the protocol to increase its utility.
Nevertheless, the lottery problem can be solved by the tournament tree protocol, which employs a commitment scheme based on standard assumptions such as one-way functions. Even though one cannot prove security in the strongest sense that the winner is unbiased, the tournament tree satisfies some game theoretic notions of security. For example, an honest agent following the protocol will be guaranteed at least the same probability of winning, even if all other agents conspire against it. Moreover, agents forming a coalition also cannot increase their combined chance of winning.
Inspired by this framework, we will extend the game theoretic notions of security to protocols solving more general assignment and selection problems. However, unlike the lottery problem in which all agents have the same preference, it is known that the more complicated problem structure implies some impossibility results. For instance, even with a trusted authority, there is no mechanism for a general assignment problem that can achieve all the following properties simultaneously: truthfulness, Pareto optimality, equal treatment. Hence, even formulating the right security notions for protocols realizing the mechanisms for such problems is a challenging task.
Finally, to have practical impacts, our protocols will also achieve communication efficiency. Since our preliminary work shows that the tournament tree protocol has optimal round complexity under some security requirement, we will explore approximate notions of security, and design protocols that have desirable tradeoffs between security and communication efficiency.