A Crash Course on MPC, Part 7
Honest-Majority MPC with Active Security
Happy new year!
In the previous lecture I presented an actively secure protocol supporting t<n/3 corruptions. Recall that an active adversary is allowed to make corrupt parties deviate arbitrarily from the protocol specification, and to ensure that the computation was still correct we had to rely on error correcting/detecting properties and hyper-invertible matrices. If we want to tolerate more corruptions, say at most t<n/2, it is natural that the complexity of the protocols will increase, at least if we insist in maintaining active security. This is precisely the goal of this post. We already saw a passively secure protocol in the honest majority setting back in lecture 4. What I will present below is an “extension” of this protocol to withstand active adversaries.
We already have a protocol for active security with t<n/3, so the first thing should be to explore what breaks when the number of corruptions goes above the bound n/3, up to n/2. There were three critical parts in that protocol that required our attention when the adversary was active: (1) reconstructing shares [x] of degree t, (2) reconstructing shares <x> of degree 2t, and (3) preprocessing pairs ([r],<r>). Reconstructing shares of degree t is not really a problem, given that error detection is still possible in this case. The problem lies with anything that has to do with shares of degree 2t: It could be the case that n=2t+1, and in such situation any set of n shares will be consistent with a polynomial of degree 2t, so there will be no way to detect that the corrupted parties changed their shares.
Let’s analyze this attack in more detail. Let’s assume (for the rest of this lecture) that n=2t+1, and suppose the degree-2t shares of some value x are (x1,…,xn), which means that xi=f(i) for a polynomial f(X) of degree at most 2t, such that f(0)=x. Recall from the lecture on Shamir secret-sharing that there exists coefficients c1,…,cn such that c1*x1+…+cn*xn=x. Let’s assume that the corrupt parties are P1,…,Pt, and suppose that they change their share from xi to xi+di, where di is some error that the adversary wishes to introduce. In this case, the reconstructed value will be
which is equal to x+d, where d=c1*d1+…+ct*dt. Observe that the adversary knows the di values, and the ci coefficients are public knowledge. The conclusion is then that the adversary can cause the reconstruction of a degree-2t sharing to be off by an additive amount d that is known to the adversary. This is bad of course! But as we will see, it is not as bad as it could be, and we can still fix this issue. It would be much worse if the adversary could cause the opening to be whatever value he chooses (e.g. cause <x> to reconstruct to 0), or even worse, something related to the original secret beyond just adding the error d (e.g. <x> reconstructs to x² or to 2x).¹
Multiplication with Faulty Openings
Let’s recall how the multiplication protocol from lecture 4 works. The inputs are two shared values [x] and [y], and the goal is to compute [x*y] with the help of a double-sharing ([r],<r>). To do so, the parties proceed as follows:
- Compute <x*y> = [x]*[y] by locally multiplying the shares of x and y. Compute <x*y-r> locally.
- Open this shared value to get x*y-r.
- Compute locally [x*y] = [r] + (x*y-r).
As discussed above, however, under the presence of an active adversary the openings of degree-2t shares maybe incorrect by an additive amount known to the adversary. In our case, this means that the opening of <x*y-r> may lead to x*y-r+d, where d is some additive error introduced by the adversary, and therefore the value that the parties may end up computing at the end is [r]+(x*y-r+d) = [x*y+d], that is, the result of the computation is off by the exact same additive amount that the adversary chose when cheating in the opening of the degree-2t sharing.
Let’s recap what we have seen so far. Opening degree-2t shares is “doomed”, in the sense that the adversary can cheat and make the honest parties to reconstruct an incorrect value. However, this value is still related to the original shared value in a very specific way: It is equal to the correct value plus some error that the adversary chooses. When computing multiplications, this error carries over to the result of the product, causing it to be incorrect. It may look as if we didn’t make much progress, but we actually did! As we will show below, we can actually check that there was no error in the multiplication. This turns out to be very interesting: Opening degree-2t shares on its own won’t give you any way to check that the result is correctly opened, but if you use them to compute a multiplication, you can actually check that the product is correct, and hence that the value was correctly opened to begin with! Pretty cool.
Double Sharings
First, in the protocol above we assumed the parties had a double share ([r],<r>). These can be generated with passive security using the DN07 protocol by Damgård and Nielsen from CRYPTO 2007. It turns out that this protocol can be extended (also presented in the same paper) to achieve active security, so I will assume from now on that the parties have access to such pairs. You may ignore the rest of the paragraph, but for those who are interested, the general idea to achieve active security is that the exact same protocol as in the passive case works, except that it must be guaranteed that the shares distributed by potentially corrupt parties are consistent with a polynomial of the right degree. To achieve this, it is possible to take a random linear combination of the values shared by the parties and check that the result is consistent by announcing its shares. I would love to get more into detail with this but there is way more to go below.
Faulty Multiplication Triples
Let’s recap the concept of multiplication triples, which was discussed several lectures ago. A multiplication triple is a tuple ([a],[b],[c]), where a and b are random and c=a*b. These were introduced in lecture 2, and back then they were used to help the parties securely compute multiplications, in a similar way as double-sharings can help the parties to compute multiplications too. I will leave it as an exercise to you to prove that, if the parties have access to multiplication triples, then we can actually forget about everything discussed so far, and the parties can securely compute multiplications (that is, get [x*y] from [x] and [y], correctly) by simply using a multiplication triple. As a hint, try to adapt the protocol from lecture 2 to our setting here, and analyze what happens when the adversary is active.
Given the above, I do not want to assume that we have multiplication triples available. However, a weaker notion, which I call faulty multiplication triples, turns out to be enough for the purpose of checking that the product above [x*y+d] is correct. A faulty triple is simply a tuple ([a],[b],[c]) where a and b are random, and c=a*b+e, where e is some error chosen by the adversary. These triples are very easy to generate: (1) take random values [a] and [b], which could be obtained for example from double-sharings by discarding the degree-2t part, (2) use the multiplication protocol presented above to multiply [a] and [b], which leads to [a*b+e].
Verifying the Correctness of Multiplications
Now we are ready to mix the ingredients discussed so far to obtain a secure multiplication protocol that is also correct. So far, we have a protocol in which the parties can get [x*y+d] from [x] and [y]. The goal is to check that d=0. This can be done with the help of a faulty multiplication triple ([a],[b],[a*b+e]) as follows:
- The parties sample some random public value s. This could be obtained, for example, by getting a random shared value [s] from a double-sharing and then opening it.
- The parties compute locally [f]=s*[x]-[a] and [g]=[y]-[b], and open these values.
- The parties compute locally [z], defined by the equation below, open this value, and check that it equals 0:
The claim is that, if the value of z equals zero, then it is because d was zero to begin with, at least with very large probability. To see this, observe that by using the definition of f and g we have that z=e-s*d, so this value being zero translates into s*d=e. If d is not zero, then we could divide by it at both sides to obtain s=e/d, which shows that the random value s must be equal to the value e/d, which was determined by the adversary before s was sampled. This can only happen with small probability if s is chosen from a large enough domain, which shows that d must be zero, and in particular, the multiplication [x*y+d] was correct.
The protocol above may look a bit too obscure, so let me try to provide some intuition on it. On the one hand, the parties multiplied [x] and [y] to obtain [x*y+d]. We can “re-randomize” this multiplication by multiplying [x] and [x*y+d] by s. On the other hand, the parties also have a (faulty) multiplication triple ([a],[b],[a*b+e]), which could be also used to multiply [s*x] and [y], and would lead to [s*x*y+e] (please refer to the exercise I left a few paragraphs above, and check this fact). The intuition behind the check is to verify that these to multiplications yield the same result by subtracting these and checking that it equals 0. This subtraction would yield [s*d-e], which is hard for the adversary to make zero unless d=e=0.
As a final note, observe that if there was no randomization, that is, if s=1, then the adversary could pass the check very easily by setting d=e. As we saw above, we can only ensure that d=0 with certain probability, that we can make as large as we want by sampling s from a large enough domain. However, there is always this very very tiny probability with which the adversary may get away with cheating with a non-zero d. This is unfortunately unavoidable: Recall from lecture 1 that an honest majority MPC protocol with active security must either rely on computational assumptions, or have some small failure probability.
Other Approaches for Checking Multiplications
What we saw above is a protocol for securely multiplying two shared values [x] and [y]. The protocol proceeds in two steps: First, a double-sharing is used to obtain a potentially incorrect result [x*y+d], and then a faulty triple is used to check the correctness of this product. This is conceptually a very simple protocol, but there are in fact more efficient ways of checking that the product is perform correctly. The check we presented above adds an overhead to every single multiplication that appears in the computation. This recent work of Goyal and Song shows how one can check that all the multiplications in the computation are carried out correctly with a communication complexity that is essentially independent of the amount of multiplications! Hence, one can say that the complexity of running honest majority MPC with active security is practically the same as with passive security, pretty cool.
Footnotes
- ¹ All the lectures so far assume that, when reconstructing, the corrupt parties do not look at the shares from the honest parties before announcing their own shares. Otherwise, the adversary learns the secret before the honest parties and then he can modify the corrupt parties’ shares so that the shares reconstruct to any desired secret. This can be enforced by letting the parties first announce a hash of their share (a short string that somehow “summarizes” their share without leaking it) and only after this has been done, they announce their actual shares and check that they are consistent with the hashes distributed earlier. More generally, we say that the parties commit to their shares somehow before actually announcing them.
