MPC Techniques Series, Part 2: Security Taxonomy and Active Security
By Claudio Orlandi, Associate Professor and Chief Cryptographic Protocol Designer at Partisia
Last week’s blog titled “Secret Sharing” explained how to securely compute on secret data using a special technique known as “replicated secret-sharing”. Informally, we argued that using this technique, no single participant will ever learn any of the secrets they are computing on.
However, we have not yet defined what secure means in this context. Since this blog series is about secure multiparty computation, this post will focus on some of the most common taxonomy for security levels in multiparty computation, with a particular focus on active security.
Passive Security
One way of describing a passive adversary in an MPC protocol is by considering someone that is capable of breaking into the machines of participants of the MPC protocol and looking at their internal state, without the ability to replace the code they are running in the protocol. This kind of adversary is also referred to as honest-but-curious (to stress that the adversary follows the protocol but might try to infer more information, analyzing all information that they might be able to gather) or semi-honest. Looking back at the protocols from the previous blog, we can see that the information gathered by any single server isn’t sufficient to reconstruct any of the secrets.
Multiple Adversaries?
If several participants are corrupt at the same time, we always assume that the adversary has access to the state of all of them. In other words, it is common practice to assume that there is a single, “monolithic” adversary that controls all corrupt parties or that the multiple adversaries are willing to cooperate among themselves. This is true both for passive security and for the other levels of security.
Active Security
In practice, if you are performing secure computation with a group of servers over the internet, it is safe to assume that you don’t really trust the people you are interacting with, and you might be worried that they won’t follow the protocol as instructed. Thus, the security guarantees provided by passive security might not be enough. In this case you might need a protocol which is secure against active adversaries, or in other words adversaries that might arbitrarily deviate from the protocol specification.
If a passive adversary is someone who can steal a hard-disk and inspect whatever data they find, an active adversary is someone who has followed a programming course (perhaps a cryptography course too!) and is going to change the code run by their own server to exploit any vulnerabilities in the protocol you are running with them. Active adversaries are also referred to as malicious (since they act arbitrarily and not according to the protocol) or sometimes Byzantine (following terminology from the distributed system literature).
Covert Security
When cryptographers design protocols with active security (and prove them to be secure!) they need to make sure that their protocols withstand all sorts of attacks, even some that have very little probability of succeeding, or whose outcome isn’t necessarily very convenient for the adversary. In other words, if an active adversary was a villain from a superhero movie, it would be more like the Joker from the Batman (“some people just want to watch the world burn!”), rather than a James Bond villain with an elaborate plan. Therefore, cryptographers have also coined the notion of a covert adversary e.g., an adversary who might deviate from the protocol, but who does not want to be caught because they are, for example afraid of consequences or loss of reputation. In some cases covert secure protocols can be more efficient than actively secure ones, while still providing meaningful security guarantees (e.g., if the other party tries to cheat it will be detected with 99% probability).
Is Passive Security Ever Enough?
While active security is preferable in practice, there are some notable examples in which passive security might be sufficient. First, if there is any way of making sure that the code can’t be changed (e.g. you ship your MPC protocol in some hardened hardware device) then passive security might be enough. Moreover, there are cases in which MPC is needed, not so much because you don’t trust who you are working with, but maybe just because due to legal requirements you are not allowed to access some data, yet you are legally allowed to learn the result of some computations performed on it (think of some researcher performing statistics on sensitive personal data). In this case, implementing a passively secure MPC solution might still be enough to comply with existing regulations and in particular to assure that you never had access to any data you were not supposed to access. Finally, most actively secure MPC protocols are constructed starting with a passive secure protocol and then adding all sorts of bells and whistles to make them secure against active adversaries. Therefore, passive security is a good starting point to learn about MPC.
Attacking the Replicated Secret Share Protocol
The main issue with actively secure protocols is that they are usually much more complex and inefficient when compared with their passive secure counterparts. But to make things slightly more concrete, I will now give a very simple example of how the protocol from the previous post can be hardened to withstand active attacks.
Remember that in replicated secret sharing we split a secret x into a number of shares (or random numbers) x1 … xn such x=x1+x2+…+xn, and then we give each server a subset of these shares. In our previous post we had 3 servers who got 2 out of 3 shares each.
Consider the last step of the computation, where the parties have to reconstruct the output of the function. Here any 3 of the servers could simply send their shares to each other, and they can then reconstruct the output x=x1+x2+x3.
This works well when dealing with passive adversaries, but consider now what happens with active adversaries: if one of the servers is controlled by an adversary, the adversary can of course lie about the value of their shares. For instance, a server might send x3’=x3+1 instead of x3. Thus leading to an incorrect output of the computation.
How big of a problem is this?
Remember the running example of unanimous voting from our previous post, where we wanted to know if everyone agreed on a proposition or, in other words, if all parties had input 1. This was achieved by simply multiplying together all inputs, which results in 1 if all inputs are 1, or 0 if at least a single input is 0.
Now a corrupt server can force the output of the vote to be 1 using the following strategy: the corrupt server inputs 0 (signifying NO) to the computation. By voting 0 the server makes sure that the output should be x=x1+x2+x3=0 (due to the correctness of the protocol). But then the server adds 1 when it’s time to reveal their share forcing the final reconstructed output of everyone to be 1 — even if someone else voted 0=NO!
Active Security via Redundancy
One simple way to deal with this problem in the protocol is to add extra redundancy. Say now instead of having 3 servers we have 6 servers, call them Server 1 to 6. We still split a secret x into three shares x=x1+x2+x3.
We still give server 1, server 2 and server 3 the same shares as before, that is (x1,x2),(x2,x3) and (x3,x1) respectively. In addition we give server 4 the same shares as server 1, to server 5 the same shares as server 2 and so on. Moreover, every time server 1 does a computation in the protocol, server 4 does the same computation. And every time server 1 sends a message to the other servers, server 4 sends the same message. When one of the other servers receives a message from server 1 and 4, they check that they are the same. If they are not, the server complains and raises a flag saying “someone is cheating”.
Adding new servers didn’t change the privacy guarantees of our protocol (that is, no single server can learn anything about the secrets), but now we also get some form of robustness in the sense that any single server cannot force the output of the computation to be incorrect.
Note, the technique to achieve robustness is quite inefficient. In this example with 6 parties we can only tolerate one corrupted server (if both server 1 and server 4 are corrupt in the example above they can both lie about their shares in a consistent way, and they will not be detected). Shamir secret sharing, which Ivan will present in the next post, can also be used to guarantee robustness against a higher fraction of corrupted servers with much better performances.
About the author:
Claudio is Associate Professor in Computer Science at Aarhus University and co-founder of Partisia Infrastructure. He is a leading researcher on secure multiparty computation and zero-knowledge protocols. Claudio has a broad interest in the theory and practice of cryptographic protocols, with a focus on efficient constructions of advanced cryptographic primitives, threshold cryptography, privacy-preserving technologies, theory and practice of cryptographic protocols.
