Chapter 3. Multi-Party Computation

Dominik Raub

Eduardo Soria-Vázquez

ulti-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.iii researcher.They would have not been the same without the support of family, friends and colleagues.I would like to start by thanking Nigel Smart for giving me this opportunity, being my advisor and introducing me to others in the community.Martijn Stam

S Zaky Mohamed

Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek

The central objects of secure multiparty computation are the “multiparty functions” (or functionalities) that it seeks to securely realize. In this chapter we survey a set of results that constitute a Cryptographic Complexity Theory. This theory classifies and compares multiparty functions according to their secure computability and reducibility to each other. The basic questions studied, under various notions of security and reducibility, include:

Dominique Unruh

Oded Goldreich

The design of secure protocols that implement arbitrarily desired functionalities is a major part of modern cryptography. Taking the opposite perspective, the design of any cryptographic scheme may be viewed as the design of a secure protocol for implementing a suitable functionality. Still, we believe that it makes sense to differentiate between basic cryptographic primitives (which involve little interaction) like encryption and signature schemes, on the one hand, and general cryptographic protocols, on the other hand. In this chapter we consider general results concerning secure multi –party computations, where the two –party case is an important special case. In a nutshell, these results assert that one can construct protocols for securely computing any desirable multi–party functionality (see the following terminology). Indeed, what is striking about these results is their generality, and we believe that the wonder is not diminished by the (various alternative) conditions under which these results hold. Our focus on the general study of secure multi–party computation (rather than on protocols for solving specific problems) is natural in the context of the theoretical treatment of the subject matter. We wish to highlight the importance of this general study to practice. Firstly, this study clarifies fundamental issues regarding security in a multi–party environment. Secondly, it draws the lines between what is possible in principle and what is not. Thirdly, it develops general techniques for designing secure protocols. And last, sometimes it may even yield schemes (or modules) that may be incorporated in practical systems.