listen to this article:
Secure multiparty computation, otherwise known as MPC, has been studied in academia for decades, taking it from theory to a practical technology. As a result, it is now being used commercially to solve different privacy and security problems. In this blog, we will describe what multiparty computation is and what security problems it can solve today.
What Is Multiparty Computation?
MPC is a cryptographic protocol where a number of distinct, yet connected, computing devices (or parties) wish to carry out a joint computation of some function while preserving certain security properties in the face of adversarial behavior.
Secure Multiparty Computation Example
In order to be concrete, consider a group of friends – all working in the same industry – who wish to compute basic statistics on their salaries. They may wish to know the average salary for those with 0-2 years’ experience, 3-5 years’ experience, and greater than 5 years’ experience. This would enable them to understand if they are being underpaid, or in general where they are on the scale (don’t worry, no one thinks that they are overpaid).
Until now, in order to carry out such a computation, they would have to provide this information to a trusted third party who would receive their information, compute the statistics, and send back the results. The basic idea of MPC is to enable a set of parties to carry out such a computation without any trusted party (because usually, no such trusted party exists). We call such a process an “MPC protocol”.
MPC Protocol Requirements
The concept of MPC considers an adversarial setting, where some of the parties (or an external entity) try to “attack” the protocol. The aim of such an attack may be to learn private information (e.g., the salary of some of the participants) or to cause the result of the computation to be incorrect (e.g., that the average salary is some specific value so that they can offer someone in the group a job and have them think that their offer is good).
As such, two of the most basic security requirements for an MPC protocol are privacy and correctness. The privacy requirement states that nothing should be learned beyond what is absolutely necessary; more exactly, parties should learn the designated output and nothing else. The correctness requirement states that each party should receive its correct output. Therefore, the adversary must not be able to cause the result of the computation to be different from the function that the parties had set out to compute.
Although relatively straightforward as a high-level notion, the devil is very much in the details. When considering the security guarantees of MPC:
- How can we actually formally state these requirements of privacy and correctness?
- What type of adversary are we protecting against, and with what adversarial power (can the adversary can run malicious code)?
- Do we assume that the adversary controls any size subset of the parties or only up to a certain percentage?
History and Feasibility
MPC was first formalized in the late 1980s and over the past decades have developed into a major area of research in cryptography. MPC has a rich and elegant theory based on strong scientific foundations. Amazingly, it has been proven that everything that can be computed given all inputs can be computed in MPC (while the inputs are kept private). This means that in principle MPC can be used in any application where parties need security guarantees over their inputs.
However, it doesn’t mean that we can compute everything in MPC with high enough efficiency to be practical. In order to address this, research in applied MPC has blossomed over the past 10-15 years, bringing MPC to a point where many real-life problems can be solved utilizing it. This has in turn led to the commercialization of MPC and its use in practice. As someone who started researching MPC in 1998, when it was pure theory, it is extremely satisfying to see how far we have come in so little time.
The Science Behind MPC
It is instructive to see how it is possible to compute information without revealing it.
Consider a set of people who wish to compute the average of their salaries without revealing to anyone at all their personal salary:
- We can number the parties from the first to last, in any arbitrary order.
- Then, the first party chooses a very large random number, adds their salary to the number, and forwards the result to the second party.
- The second party adds their salary to the value they received and forwards the result to the third, and so on to the end.
- The last party adds their salary and sends the final result to the first party.
- Finally, the first party subtracts the original large random number and divides the result by the number of parties. This is the average (since it is just the sum of all salaries divided by the number of parties). In order to see why this preserves privacy, note that the large random number chosen by the first party hides its own salary and all intermediate sums of the salary (as long as it is large enough). Thus, no individual party sees anything but a large random number.
- Finally, the first party receives the sum of the salaries, but this is actually equivalent to the average (given the average, multiplying by the number of parties gives the sum of all salaries; thus, this reveals nothing more than the average).
The result is that no party learned anything about anyone’s salary, but they still are able to learn the average. Magic! (Actually, I hate calling it magic; it’s just science.)
How Secure is the MPC Protocol?
Note that this protocol is actually only secure as long as at most one party is corrupted. However, if two or more may be corrupted, then it is no longer secure.
Concretely, consider the case that the 3rd and 5th parties are corrupted. These two corrupted parties can collude to learn the 4th party’s input by subtracting the value sent by the 3rd party to the 4th from the value sent by the 4th party to the 5th.
In addition, nothing prevents the first party from lying about the final result. Thus, if all parties are supposed to learn the average, the protocol needs to be modified to prevent the first party from changing the result. Techniques exist to solve all of these problems.
Cryptographic Applications of Secure Multiparty Computation
Classically, MPC deals with the problem of enabling different parties to collaborate, while preserving the privacy of their individual inputs.
One example of such a use case is the problem of comparing a person’s DNA against a database of cancer patients’ DNA, with the goal of finding if the person is in a high-risk group for a certain type of cancer. Such a task clearly has important health and societal benefits. However, a person’s DNA is highly sensitive, and should not be revealed to private organizations (see here for good reasons why). This dilemma can be solved by running a secure multiparty computation protocol that reveals only the category of cancer that the person’s DNA is close to (or none).
In this example, the privacy requirement ensures that only the category of cancer is revealed, and nothing else about anyone’s DNA (neither the DNA of the person being checked nor the DNA of the patients in the database).
Another example application is to use MPC to enable multiple banks to run risk analysis and fraud prevention algorithms over the data that they all hold in entirety, instead of each running the algorithms over their own data alone. This makes sense since the more data that one has, the better these algorithms perform. However, for both competitive and compliance reasons, the banks cannot actually pool their data. This dilemma can be solved by using MPC.
A completely different application of MPC relates to the case that all the data actually belongs to one party or organization. However, there is great risk in exposing sensitive secrets on any single machine where they can be stolen.
Today, network defense assumes zero-trust, meaning that attackers are in our networks and everything is potentially vulnerable. A way to defend against this is to secret-share data between two or more sites, with strong separate between them, and then use MPC to operate upon the data without ever bringing it together. This “secret sharing” method has the property that an attacker can learn nothing without bringing all of the shares together, thereby forcing them to breach multiple sites.
This use of MPC introduces a new paradigm of defense – instead of trying in vain to build an impenetrable wall around a single machine holding sensitive data, security is obtained by separation and by forcing an attacker to breach multiple separate lines of defense. We call this a “security” application of MPC since it refers to the case of one entity securing their own data.
Eliminate Single Point of Failure
One popular security application of MPC is to protect cryptographic keys from theft and misuse, by never having them exposed in any single point at any single time, and by enforcing usage policies at multiple entities. This provides the ability to protect cryptographic keys in software, providing an alternative to legacy hardware solutions that introduce many operational challenges in today’s hybrid and multi-cloud environments.