AbstractMulti-Party Computation (MPC) protocols allow a set of mutually distrustful parties to securely compute on their joint private inputs, maintaining the privacy of those. Since its early conception in the eighties, a plethora of research as well as some real world deployments have taken place, demonstrating the relevance of such an interesting mathematical problem. Nevertheless, most of the research and all deployments have focused on scenarios where both the number of parties and network latency are very low. This thesis lays out the first steps towards practical deployments of large-scale MPC, where many parties may be involved and they might only be connected through a high-latency network such as the Internet.
Both theoretical and empirical evidence shows that non-constant-round protocols cannot perform well on slow networks for many functions. In order to overcome this issue, all the works in this thesis include concretely efficient constant-round protocols based on multi-party garbled circuits. Chapter 3 and Chapter 4 deal with the very strong setting where an active adversary corrupts all but one parties. The former achieves such goal by using homomorphic encryption for low-depth circuits. The latter, based on subsequent work, improves the theoretical understanding of the problem and utilises oblivious transfer to improve efficiency.
In Chapter 5 we provide both constant and non-constant round protocols that can handle large numbers of parties more efficiently. We leverage our performance improvements by relaxing the setting where all but one parties are corrupted to one where a small minority of honest participants can be assumed. Concretely, such change allows to distribute secret key material so that each party only holds a ‘short’ part of the key. Security is then based on the concatenation of all honest parties’ keys rather than on each party’s individual key, improving both the communication and computation complexities.
|Date of Award||5 Feb 2019|
|Supervisor||Nigel Smart (Supervisor)|