Have you ever wanted to know what the average salary of the employees in your organization is, without wanting to reveal your salary? What about wanting to know the result of an exit poll, without revealing you vote? Or having YouTube recommend interesting videos, without learning your interests?
Sounds contradictory? At a high level, this is what Multi Party Computation (MPC) tries to achieve. In all the above examples, we want to know the result of something which not only depends on us but also on others in our “network.” A distributed system consists of a network of computers that communicate with each other. Together, the computers want to achieve a common goal, which can be thought of as a function. Each computer in the system is a “party,” who has a private input to this function. The idea is that while jointly computing the function, no party must be able to learn the input of any other party in the network. To do this, the parties run a “protocol,” which decides messages to be sent based on messages received. At the end of the protocol, the parties have communicated enough with each other to be able to compute the function output.
An important aspect of a distributed system is the type of network over which the parties communicate. In a synchronous network, all parties are assumed to be available, or “online”, at the same time. Thus, it is assumed that messages can be delayed only by a certain amount of time. Protocols running in synchronous networks proceed in “rounds,” and have a fixed execution time. On the other hand, in an asynchronous network, different parties may come online at different times. Protocols running in asynchronous networks are event-based and do not have a fixed execution time. These protocols are more complex when compared to their synchronous counterparts.
Typically, during Multi Party Computation, it is assumed that the underlying network is either synchronous or asynchronous, and that the parties know the network type beforehand. But what if we envision a scenario where the participants are unaware of the exact network type? Can we have a single protocol that works irrespective of the underlying network, and which provides the security guarantees of synchronous protocols if the network is synchronous, and asynchronous protocols if the network is asynchronous? Our paper answers this question in the affirmative and opens up a variety of interesting questions in what we call the “best-of-both-worlds” setting.
