A Crash Course on MPC, Part 4
Honest-Majority MPC with Passive Security
In the previous blog you learned about Shamir secret-sharing. Recall that in this linear secret-sharing scheme, a secret s is distributed among n parties P1, …, Pn by sending f(i) to party Pi, where f(X) is a random polynomial of degree at most t, restricted to f(0) = s. This ensures that no set of at most t shares leaks anything about the secret, and any set of at least t+1 shares completely determines the secret. All this happens over a field that is sufficiently large, say, integers modulo a prime that is larger than n+1. The goal of this post is to show how use this linear secret-sharing scheme to enable secure multiparty computation in an honest-majority setting, with perfect security against passive adversaries.
Let’s start by recalling some notation. We denote by [x] the “fact” that a value x is secret-shared among the n parties using Shamir secret-sharing. We saw in the previous lecture that if the parties have shares of two values x and y, then they could locally add their shares to obtain shares of x+y. This is denoted by [x+y] = [x] + [y]. Also, recall from the previous lectures that, to get MPC for any function you may think of, it suffices (at least in theory) to devise protocols for adding and multiplying secret values. The observation above gives us a method to handle additions, so it suffices to develop protocols for multiplying secret-shared values, that is, obtaining [x*y] from [x] and [y]. This is precisely what this post is about.
For the rest of the post I will consider an adversary that can corrupt at most t parties. I will work in the setting of honest majority with passive security, meaning that t<n/2 and the adversary is assumed to behave correctly during the protocol execution. Active adversaries will be discussed in subsequent posts. Furthermore, for the sake of simplicity I shall assume that n=2t+1, although this is not strictly necessary for the protocols to work and it’s just for convenience in the notation.
Secure Multiplication via Resharing
Let’s start by discussing a very simple multiplication protocol that is not very efficient, although it’s very simple and easy to understand. The protocol is rooted in the following idea. Assume the parties have shares of two values [x] and [y] using polynomials f(X) and g(X) respectively, that is, party Pi gets f(i) and g(i) as the shares of x and y, and the polynomials satisfy f(0) = x and g(0) = y. As recalled above, each party Pi can locally add f(i)+g(i) to obtain shares of x+y. This is because f(i)+g(i) is the evaluation of the polynomial q(X)=f(X)+g(X) at the value i, and this polynomial has the right degree (at most t) and it satisfies q(0)=x+y. A natural question is whether or not a similar property holds for multiplication. It is true that the multiplication of Pi’s shares, f(i)*g(i), is the same as h(i), where h(X) is the polynomial f(X)*g(X). This polynomial does satisfy h(0)=f(0)*g(0)=x*y, which gives us hope, but unfortunately it doesn’t have the right degree: Since f and g have degree at most t, h has degree at most 2t, which is not good enough for the parties to get shares of x*y.
We have seen that the parties can locally get shares of x*y, but under Shamir secret-sharing scheme with degree 2t rather than t. This is not entirely bad: 2t+1=n shares can be used to reconstruct the secret, so the parties can still obtain x*y. However, this does not scale beyond one single multiplication, and what we would really want is to obtain shares of x*y under Shamir secret-sharing with degree at most t so that the computation can continue with the same sharing scheme. One potential solution involves a technique known as resharing, and here is how it works. Using the notation from above, if each party multiplies their shares together then they get shares h(i) of x*y, where the polynomial h(X) has degree at most 2t. As recalled above, 2t+1=n shares together can reconstruct the secret. More importantly, this reconstruction is “linear”, in the sense that there exist constants c1, …, cn such that h(0) = c1*h(1) + … + cn*h(n) (revisit the lecture on Shamir secret-sharing if this does not ring a bell).
The observations above can be used to get shares [x*y] of the right degree as follows. Each party Pi will take their new “share” h(i), and it will distribute shares of degree t of this value to all the other parties. This leads the parties to obtaining shares [h(i)] for each i=1,…,n. Since this secret-sharing scheme is linear, the parties can locally take any linear combination with public coefficients to obtain shares of the corresponding result. In this case, we can use this so that the parties take the linear combination c1*[h(1)]+…+cn*[h(n)], which leads to parties to obtain shares [h(0)], and since h(0)=x*y, voilà! Observe that the protocol is perfectly secure as the only thing that the adversary receives are shares, that are not enough to learn anything about the corresponding secrets.
Secure Multiplication via Double-Sharings
The protocol described above does work and as promised, it is easy to understand (I hope you did find it to be the case), but it suffers from two major weaknesses. First, it is very hard to extend to active security: If corrupt parties are allowed to deviate arbitrarily, then there is no guarantee that the right value h(i) is used in the resharing step, which in turn can lead to some concrete attacks. Secondly, the scheme is not very efficient: The resharing step requires each party distributing shares to all other parties, which incurs in a total communication complexity of n². In this section I discuss a different approach to secure multiplication that leads to an asymptotic communication complexity of O(n). This means that, per party (that is, dividing by n), the communication is constant! Independently of how many more parties join the computation. Pretty cool huh.
The only downside of this method is that, unlike the resharing protocol described above, it requires preprocessing. I will begin by describing the online phase, and then we will end by discussing the offline phase in which the necessary preprocessing material is generated.
Online Phase
Recall that in our setting that parties have shares [x] and [y], and the goal is to compute [x*y]. The preprocessing material we will use for this protocol consists of a random value r that is unknown to any party and is secret-shared twice, using Shamir secret-sharing, but with two different degrees: t and 2t. I will keep the notation [z] to denote a sharing of z using degree-t polynomials, and I will introduce the notation <z> to denote degree-2t sharings of z. Under this notation, the preprocessing material looks like ([r],<r>), which is called a double-sharing.
We will discuss how to generate these in the upcoming section. For now, let’s just assume we have access to one such pair ([r],<r>). The protocol to obtain [x*y] goes as follows. First, recall from our first protocol above that the parties can locally obtain shares of the product x*y, but using a polynomial of degree 2t instead of t. With our new notation these sharings can be written as <x*y>. The goal now is to use the double-sharings ([r],<r>) to obtain [x*y] from <x*y>. This is accomplished by letting the parties exploit the linearity of the degree-2t scheme to locally compute <x*y-r>, followed by the parties reconstructing this value by joining their shares, so that they now learn x*y-r.¹ So far nothing has been leaked about x, y, nor their product, because the value r is random and unknown to any party, which effectively masks x*y. Now, the parties can use the linearity of the degree-t sharing to add the public value (x*y-r) with the sharing [r], which leads to (x*y-r)+[r] = [x*y], as desired.
Offline Phase
For the protocol above we made use of a preprocessed double-sharing ([r],<r>). Now we discuss how to get one such pair. Let’s begin with a very simple protocol. Each party Pi will sample a random value Ri, and then it will secret-share this Ri towards the parties using both degree-t and degree-2t sharings. At this point the parties have shares ([Ri],<Ri>) for i=1,…,n, where Ri is random but known to party Pi. Now, the parties can add these shares together to obtain [r]=[R1]+…+[Rn] and <r> = <R1>+…+<Rn>. This value r is random, being the sum of random values, and it is unknown to the adversary since the Ri’s corresponding to honest parties “mask” the result r. We can improve this protocol by asking only t+1 parties to distribute shares of some Ri, since there will be at least one honest party in the sum and therefore the result will still look random and unknown to the adversary.
The only downside of the protocol sketched above is its communication complexity: Each party must secret-share a value towards the other parties, and, as in the resharing protocol described at the beginning of the post, this leads to a communication complexity of n². Even with the optimization discussed above where only t+1 secret-share an Ri, we still reach a complexity of ~n² since t+1 is roughly n/2. Achieving O(n) complexity is a bit harder, and the brilliant idea I will discuss next comes from a paper by Damgård and Nielsen at CRYPTO 2007, the so-called DN07 protocol. The intuition of the protocol is the following. Currently, we’re making use of n random values Ri to generate only one random value r, in spite of there being n-t=t+1 values that are unknown to the adversary (that is, these corresponding to the honest parties).
The main idea of the DN07 protocol is to use these t+1 random values unknown to the adversary to generate t+1 random values that are unknown to any party. The main challenge here lies on the fact that we don’t know the identities of the honest parties! So somehow we need to “extract”, from all of the n sharings, t+1 sharings that look random and unknown to the adversary, without knowing which of the original sharings are honest. Suppose that parties P1,…,Pn distributed the shares ([R1], <R1>), …, ([Rn], <Rn>). The idea is to use a (k times n) matrix M, and multiply the vector ([R1], …, [Rn]) by this matrix (also for the <.> sharings), and get the sharings ([S1], …, [Sk]). If M satisfies the property that the (k times k) matrix formed by any subset of k columns is invertible, and if k=n-t, then all of the resulting values S1, …, Sk would satisfy the desired condition of being random and unknown to the adversary. To see this, simply take the columns corresponding to the indexes of the k=n-t honest parties, and observe that, because of the properties of M, the vector (S1, …, Sk) is in a one-to-one correspondence with these honest secrets. Finally, such an M matrix exists: Choose n different points a1, …, an, and set the (i, j) entry to be aj^(i-1). I leave it as an exercise to check that this matrix satisfies the desired property.
Footnotes
- ¹ Naively, reconstructing a shared value involves all parties sending their shares to all other parties, which leads to a communication complexity of O(n²). This can be improved by letting each party send his share to a central party, say P1, who reconstructs and returns the result to all other parties. As described this only works for passive security since the central party may lie about the reconstruction, but as we will see later on this can be extended to active security without hurting communication by much.
