By Claudio Orlandi, Associate Professor and Chief Cryptographic Protocol Designer at Partisia
This is the first in a series of blog posts, titled ‘MPC Techniques’, which we will be publishing every week for the next 9 weeks. In each blog, we will be presenting some of the basic techniques which can be used to implement MPC, which will likely be of interest to developers and those with a mathematical or technical background. This first chapter focuses on secret-sharing.
As Ivan has explained in a previous post titled, ‘Multiparty Computation: The beacon of privacy solutions explained’, secret-sharing is one of the fundamental tools for building MPC protocols, as it allows pieces of a secret (private information) to be stored on different servers in such a way that no server can learn the secret, yet the servers together can perform computation on the secret itself. For example, a number of employees could compute the average of their salaries without having to disclose their individual salaries to each other.
This blog post will teach you how secret sharing can be used to securely evaluate any function.
What is Computation?
In the context of MPC, functions are typically described as a series of mathematical operations, namely additions and multiplications. It might sound surprising but any function can be broken down into these very simple building blocks that everyone knows from school. In some cases, it is very easy to see how a function can be described using multiplications and sums, while in others this might look a bit trickier at first, but this doesn’t mean that it can’t be done.
For this blog post, let’s consider the following example: a group of individuals want to take a private and unanimous vote. That is, they want to know if they all agree on some proposition (e.g., which movie should we go watch together) but in case anyone disagrees no one should learn who or how many people disagreed. How can we compute this function using only additions and multiplications?
In other words, each participant has an input which is either YES or NO. First of all, we could all agree that 1 means YES and 0 means NO. Now the inputs are numbers, and therefore it is easier to perform computation on them. Then, by remembering that 0 times anything gives 0, one can implement the unanimous vote by simply taking the product of all the inputs. Now, if any of the inputs are 0 (that is, if anyone disagrees on the proposition), the outcome will be 0. And if everyone agrees (that is, if all the inputs are 1), the output will be exactly 1. So, we now have an arithmetic circuit that can be used to implement our function. But how can we implement this function using MPC?
Multiplication of Secret-Shared Values
In our previous blog post titled ‘Multiparty Computation: The beacon of privacy solutions explained’, you may have learned that to secret-share a secret value (for instance, the secret votes 0 and 1 from above) you can pick a bunch of random numbers that add up to the secret, and store the random numbers on different servers. Since each number is random, by themselves they give no information about the secret. But if you can gather all the pieces, then you can reconstruct the secret. For instance:
0 = 3-5+2
Even if you know two of the shares, say 3 and 2, you have no idea what the third share is. It could be -5, in which case the secret would be 0. But it could also be -4, in which case the secret could be 1. Since there is no way of knowing which of the two cases we are in, secret-sharing offers perfect security. (For simplicity all computations here are done over the integers, but in actual MPC solutions the computations are done modulo some fixed value — this has no consequence for the high level explanation in this blog).
In the previous blog post you have also learned that (since addition is commutative) it is possible to securely compute additions of secret shared values. Say you have two secret values a and b, which are split into shares
a= a1+a2+a3 and b = b1+b2+b3
Server 1 knows a1 and b1, thus it can compute c1=a1+b1. Server 2 and 3 can do the same with their shares. It is not easy to see that if the servers combine their shares they will reconstruct the sum of the two original secrets that is:
but will not learn anything else about a and b.
However, if we want to implement the unanimous vote as described above, we need to compute products of secret values! This is slightly harder, but not impossible.
To perform multiplications of secret values we are going to introduce a technique known as “replicated secret sharing”. When using replicated secret sharing, we give each server not one, but several shares of the secrets as seen in Figure 1. Here is how it works in practice: given a secret sharing of a = a1+a2+a3 we give server 1 the shares (a1, a2), server 2 the shares (a2, a3), and server 3 the shares (a3, a1). Note that, as long as a server does not have all the shares, they have no information about the actual secret. So we can safely give two shares to each server, and still no server will learn anything about the secret votes. (Clearly any two servers have now enough shares to reconstruct the secret — this can be both seen as a problem for privacy since two colluding servers can steal the secret, but it can also be seen as a feature in terms of availability since now the secret can be recovered even if one of the servers crashes).
Let’s see how replicated secret sharing allows us to perform multiplication, as visualized in Figure 2. We now have two secrets a=a1+a2+a3 and b=b1+b2+b3. Remember that with replicated secret sharing server 1 knows the shares (a1, a2) and (b1, b2), server 2 knows the shares (a2, a3) and (b2,b3), and finally server 3 knows the shares (a3, a1) and (b3, b1). It is now possible for the servers to compute the product of a and b in the following way: Server 1, 2 and 3 compute their shares of the output as
It can now be checked that
c1+c2+c3 = (a1b1 + a1b2 + a1b3 + a2b1 + a2b2 + a2b3 + a3b1 + a3b2 + a3b3 ) = (a1+a2+a3)(b1+b2+b3)=ab
Using the protocol described above the servers can compute the product between two secret values. By repeating the process (and adding a few bell and whistles) they can in fact compute any function expressed as combinations of additions and multiplications in a secure way, By “secure” here we mean that no single server will learn anything about the secrets (except for the output of the computation).
The Devil is in the Details …
You might skip this section if you are happy with the overall explanation above. But the attentive reader might have noticed that at the end of the protocol each server has a single share of c1, thus we are no longer in the “right” format of replicated secret sharing (where each server holds two shares for each secret) which is needed if we want to keep computing multiplication.
This could be solved in the following way: server 1 sends c1 to server 3, and so on. It turns out that this is not really secure (since c1 contains information about some of the shares that server 3 did not know already, namely a2 and b2), therefore we need to re-randomize the values before sharing. In practice, server 1 picks a random value r1 and sends c1+r1 to server 3 and r1 to server 2. The other servers do something similar (as shown in Figure 3) and at the end we define the new shares of c as (c1’, c2’, c3’)=(c1+r1-r3, c2+r2-r1, c3+r3-r2). Note that each server has all the material they need to compute their two shares. For instance server 3 needs to learn c1’ and c3’. But this is easy since server 3 got c1+r1 from server 1 and picked r3 locally. Similarly server 3 computed c3+r3 locally and received r3 from server 2.
One can also check that c1’+c2’+c3’=c1+c2+c3 therefore everything works as it should.
Beyond Replicated Secret-Sharing
The protocol described above is pretty simple, but also has some severe limitations. First of all, it doesn’t scale well with the number of parties: it is possible to build a system with say n=101 servers that guarantees that no set of t=50 servers colluding with each other can learn anything about the secret. But then each server would need to store a very large number of shares for each secret, making the system quite impractical. A different secret sharing technique introduced by Adi Shamir, allows us to get past this limitation, as Ivan will explore in a future post.
Finally, either of the techniques described here (replicated secret sharing or Shamir’s secret sharing) only guarantee privacy in the case where a majority of the servers are honest (for instance, 2 out of 3) and can therefore not be used in the very important case of secure two-party computation, or in general in multiparty computation where you don’t trust any of the other participants (also known as self-trust). In one of the upcoming blog posts we will introduce techniques which will allow us to deal with this very interesting case.
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.