A Crash Course on MPC, Part 1
Basic Terminology and Essential Results
Consider n mutually-distrustful parties P1, …, Pn, with private inputs x1, …, xn, who want to compute a function y = f(x1, …, xn) while leaking only the output y.¹ In particular, the privacy of the inputs must be preserved. The goal of Multiparty Computation (MPC for short), in a nutshell, is to enable this in a way that only communication among the parties themselves is required. In particular, the trivial (and widely used!) solution of assigning the computation to a trusted third party who receives the inputs and promises to leak only the output is not allowed.
Among the n parties involved in the computation, some may have good intentions, and some may want to break the privacy of the other parties’ inputs. We call these corrupt parties. In contrast, non-corrupt parties are called honest parties. Just like we define encryption schemes to be secure if no adversary is able to learn anything about a plaintext, in MPC we define security by ensuring that no corrupt party can learn anything about the other parties’ inputs. Furthermore, some of these parties may be working together in a coordinated fashion. Given this, it is simpler to consider just one adversary who “controls” (or, coordinates) a subset of parties, and a secure protocol must ensure that such adversary, even with the power of controlling multiple parties, cannot break the privacy of the other parties’ inputs.
It is important to note that the protocol does not know what parties are corrupted! If our goal is to ensure the corrupt parties don’t learn the honest parties’ inputs, and we know who the corrupted and honest parties are, then a coming up with a secure protocol is trivial: Just ignore the corrupt parties completely, and treat any honest party as a trusted party who can compute the function in the clear. The real challenge when designing an MPC protocol (and the reason why the security notion sketched above makes any sense) is that in principle any party can be corrupted, no one is to be trusted.
Types of Adversaries
An MPC protocol has to maintain the privacy of the inputs towards an adversary corrupting certain subset of the parties. However, a natural question is what it means for an adversary to corrupt some parties! Factors like the way these parties behave, what and how many parties the adversary can corrupt, or how computationally powerful the adversary is, play a crucial role in designing MPC protocols.
Passive vs Active Adversaries
An MPC protocol is just a set of rules that each party has to follow. If these rules are followed “line by line”, then the computation should succeed and the privacy of the inputs should be preserved. However, the adversary is supposed to be an entity with malicious intentions and as such it may not be appropriate to assume that corrupt parties will follow the protocol specification faithfully.
An adversary that is allowed to instruct the corrupt parties to behave in an arbitrary way is called active or malicious. An MPC protocol that is secure against such type of adversaries is desirable, as it ensures that no matter how the corrupt parties behave, privacy of the honest parties’ inputs is always preserved. As argued above, since the corrupt parties may have high motivation to learn the other parties’ inputs, it is natural to require such level of security in MPC protocols.
On the other hand, a passive or semi-honest adversary is one that instructs corrupt parties to respect the protocol specification. No deviation from the protocol occurs, and this often makes the protocol design much simpler and efficient. Protocols that are secure against passive adversaries only tend to be simpler and more efficient, and although they may not provide a good enough level of security for some applications, they certainly serve as a good starting point for more secure protocols. Furthermore, some applications can actually benefit from this type of protocols as, in some scenarios, there is actually an incentive to behave correctly in a protocol, and the parties only want to ensure that the data is not centralized at any point of the computation.
Number of Corrupted Parties
I mentioned that the adversary can be seen as a master entity that controls a subset of the parties, but I did not say what parties he is allowed to corrupt. Naturally, the more parties the adversary can corrupt, the “easier” it becomes for him to break the privacy of the remaining honest participants. Ideally, one would have a protocol that tolerates a lot of corruptions, say, all but one corruption.² In this case, if you are an honest party, then you know the privacy of your input is guaranteed.
If we denote by t the largest amount of parties the adversary can corrupt, then the only requirement in the setting described above is that t < n. This is the strongest possible scenario, and it is known as dishonest majority. This is in contrast to the honest majority setting, in which it is required that t < n/2, that is, a majority of the parties must remain honest, or equivalently, the adversary can only corrupt a minority of the parties. In this case, protocols are not ‘so strong’ since privacy breaks as soon as the adversary corrupts half or more of the parties. However, as we will see towards the end of this post, assuming honest majority enables more efficient protocols with stronger security guarantees, so in some cases it is a worth trade-off.
Finally, another distinguishing regime is when t < n/3. This is even ‘worse’ than honest majority! In this case, we assume the adversary can only corrupt one third of the parties. However, this setting provides some other useful features like even better security and increased efficiency. Also, it may make sense in many use-cases, specially when n is very large.
Just one remark: One can also measure the adversary corruption capabilities in terms of what parties he is allowed to corrupt, instead of how many. For example, there may be settings where some parties are more easily corrupted (say, they have less security measures) than others. In this case, one can describe the adversary’s power by a list of possible sets that could be corrupted, which can be more general than the “sets with at most t parties” from above. This is what is known as an adversarial structure, and although I won’t touch these general structures in these notes, it is worth saying that they have received attention in the literature, and there are efficient protocols for these in case you’re interested!
Other Considerations
The two ‘dimensions’ mentioned above (behavior and number of corrupted parties) are the most relevant ones when it comes to describing the power of the adversary. However, there are some other dimensions that are relevant, and that I want to briefly mention here, although they won’t appear later on.
One is a static vs adaptive adversary. In the former, the adversary cannot corrupt parties “on-the-fly”, that is, he manages to corrupt some parties before the execution of the protocol and then, once the protocol starts, no more parties can be corrupted. An adaptive adversary on the other hand can decide what parties to corrupt during the execution of the protocol, perhaps basing this decision on what has happened on the protocol so far. This is bad, for example, for protocols that sample “committees” of parties randomly, with the hope of having a good proportion of honest and corrupt parties in this new set. In this case, an adaptive adversary can just wait until the committee is sampled, and corrupt as many parties as possible within this set.
Another distinction, although not really related to the adversary’s power, lies the type of network that is used for communication. Synchronous networks assume the parties have synchronized clocks, which allows the execution to happen in ‘rounds’. This removes a headache from the protocol design: If a party doesn’t send a message within certain time, the parties can make decisions based on this. This is not possible in an asynchronous network, where there is no concept of time. Finally, another distinguishing factor is the way the function f is modeled. I will have more to say about this later.
Types of Security Guarantees
Properly formalizing what it means for an adversary to “learn nothing about the honest parties’ inputs” is not trivial, and at an intuitive level it means that anything that the adversary learns from the protocol execution, could be learned in the ideal setting in which a trusted third party is used to compute the function, promising to leak only the output. This is formalized by using simulation-based proofs, a great and highly non-trivial tool to argue about the security of the protocols, but unfortunately I will not have the space to cover this.
Even if we keep the security notion at an intuitive level, we can still distinguish between different security guarantees.
Computational Security
A protocol is computationally secure if an adversary cannot learn anything about the honest parties’ inputs, unless he spends an absurd amount of computational resources. To exemplify the notion, imagine that in some step of the protocol the corrupt parties receive AES encryptions of the honest parties’ inputs, using some unknown key. If the adversary had a lot of resources, he could loop through all the keys and eventually decrypt the inputs. This security notion is often typically enough in practice, and, as we will see soon, it is in fact necessary (that is, you can’t get the ‘stronger’ notions below) for certain settings.
Statistical Security
A protocol is statistically secure if an adversary has only a very (very!) small chance of learning the honest parties’ inputs, regardless of its computational power. To get an idea of what this means, imagine that an honest party has an input that is either 0 or 1, and it sends this value, added with a random number from 0 to 100, to a corrupt party. The result could potentially lie between 0 and 101, but if it happens to lie between 0 and 100, it is hard for the adversary to tell if the input was 0 or 1. On the other hand, if the result happens to be 101, the adversary can immediately tell that the input was 1. However, this only takes place if the random value is 100, which happens with a small probability of 1/100.
Perfect Security
A protocol is perfectly secure if no adversary has any chance (not even very very small) of learning the honest parties’ inputs, again regardless of his computational power. This is the best possible notion, but it cannot always be achieved. To illustrate what it represents, imagine that an honest party’s input is the initial position of a ball in a roulette, and that the roulette is set in motion ‘at random’. If the adversary only sees the final position of the ball, it is impossible to know where it was initially, no matter how much computational power it can spend in figuring that out!
Observe that computational security is implied by statistical security, which is implied by perfect security. The last two notions are known as information-theoretic security, given that privacy holds thanks to information theory (basically probability theory), and not the assumption that certain problems are hard to solve unless a lot of computational resources are spent. Also, protocols that enjoy information-theoretic security, on top of being “more secure”, tend to be much more efficient given that they typically use simple operations, in contrast to computationally secure protocols that require working with computational assumptions that usually involve more complex operations (e.g. RSA requires working with a large integer modulus, Elliptic Curve operations are considerably more expensive that simple integer arithmetic, etc.)
Unfortunately, information-theoretic security cannot be always achieved: For t < n, only computational security can be obtained. This is particularly relevant for the case n=2 and t=1, which often pops up in practice.
Types of Output Guarantees
If an adversary is passive, or semi-honest, then there are no reasons why the protocol should not terminate: All the parties, honest and corrupt, follow the protocol specification faithfully, so the computation must eventually terminate. However, for active adversaries the story is different. In this case, an actively corrupt party may stop sending messages completely, which may hinder progression of the protocol execution. What happens with the computation when it is under an active attack is also a distinguishing factor of a protocol.
Guaranteed Output Delivery (G.O.D.)
A protocol satisfy guaranteed output delivery, or G.O.D. for short, if no matter how an active adversary instructs the corrupt parties to behave, the honest parties always obtain the output from the protocol.³
Fairness
G.O.D. cannot be always achieved. A weaker but still meaningful notion is fairness. A protocol is fair if the honest parties are guaranteed to get the output whenever the corrupt parties gets it. However, it may still be the case that the honest parties don’t get the output, but in this case, no one will get the output.
Security with Abort
The weakest possible notion is security with abort, in which an adversary can cause the protocol execution to abort (that is, stop) at any time. What is worse is that, unlike in fairness, in this case the adversary may even learn the output while the honest parties don’t. This is bad for applications such as distributed auctions, since this allows the adversary to learn the outcome of the auction while negating it to the other parties if he finds it convenient to do so.
There are multiple flavors of security with abort. In identifiable abort, the adversary may cause the execution with abort, but not without leaking the identity of one or more of the corrupted parties. This is a good notion as, in practice, this is likely to serve as a deterrent to active behavior as the reputation of a party that is detected to be corrupt is likely to suffer. There is also unanimous abort, in which all the honest parties agree that the execution stopped. Finally, there is selective abort, in which the adversary may select which honest parties will abort, but others may still believe the computation is going.
The notions described above have been listed from ‘best to worst’. However, as with the security notions from before, not all these properties can be achieved in all settings. For example, in the dishonest majority case, one has to settle with security with abort. The reason is simple: Think of the case n=2, t=1, there is always one last message in the protocol, so what happens if the party in charge of sending this message is corrupt and decides not to talk at the end? This party would have learned the output since it finished the whole protocol, but the honest party would be missing the last message, so it has to abort.
Some Essential Results in MPC
I’ve hinted multiple times above that not all security/output notions are achievable in all adversarial settings. I think it’s important to understand these trade-offs, so I summarized them in the following table.
Some indications for reading these results:
- A check mark means a protocol for that setting exists, while an X mark means that no protocol can exist.⁴ For example, protocols for computing any function in the dishonest majority setting with computational security against active adversaries exist, but they do not exist with statistical security.
- Marks in red are the most ‘important’ ones, in the sense that these imply the ones in black. For example, actively secure protocols in the honest majority setting with G.O.D. are possible as indicated by the red check mark, and these are not trivial to find. However, their existence implies the existence of protocols with weaker output notions such as fairness or security with abort, hence the black check marks. Similarly, a statistically secure protocol for dishonest majority against a passive adversary can’t exist, as indicated by the red X mark, and this implies that such a protocol can’t exist also for active adversaries.
- Also note that the lower right portion of the table is trivial (as indicated by the black-colored marks): Guaranteed output delivery, and in particular any other output notion, is always ensured if all the parties follow the protocol specification.
In the upcoming posts we will be visiting some of the positive results in the table above. The main takeaways should be these:
- Dishonest majority protocols require computational assumptions and can’t go beyond security with abort
- Honest majority protocols can achieve information-theoretic security and G.O.D.
- The strongest security notion of perfect security is only achievable if t<n/3, but if the adversary is passive it can also be achieved if t<n/2.
I hope you liked this first proper lecture on MPC. In the upcoming posts I will present a simple yet powerful paradigm for designing MPC protocols, that hopefully convinces you that the whole idea of computing on ‘hidden’ data is actually possible.
Footnotes
- ¹ One can also consider the case in which each party is supposed to get a different output.
- ² It doesn’t really make sense to allow all parties to be corrupted, as in that case there is no privacy to be preserved: The adversary already knows all the inputs as it controls all the parties!
- ³ Observe that the corrupt parties may decide to drop from the computation before it even get started! So, ‘ correct output’ here could mean that the resulting computation only takes the honest parties’ inputs into account.
- ⁴ What this means is that no protocol that can compute any arbitrary function can exist with the given conditions. However, this doesn’t rule out the existence of special-purpose protocols that compute only certain specific functions in these settings.
