A Crash Course on MPC, Part 6

MPC with Active Security for t<n/3

Cocorná — Antioquia, Colombia

The goal of this lecture is to present a protocol for MPC with active security, where the adversary corrupts t<n/3 parties. Ideally, we would allow the adversary to corrupt at most n/2 parties, but an actively secure protocol in this setting is much more complex to design, and I will postpone this for the next lecture. To get an intuition about the hardness of the honest majority setting, recall from the first lecture on essential results (here) that MPC with honest majority and active security cannot achieve perfect security, and one has to settle with statistical security. This means that, somewhere in the protocol, some very very tiny failure probability has to exist (failure as in the adversary gets to cheat successfully without being detected, for example), which in principle sounds a bit hard to achieve with the design we have been considering so far. Furthermore, the previous protocol based on double-sharings relied on opening degree-2t sharings for the multiplications, which cannot be done with active security if 2t+1=n, that is, the adversary can cause reconstruction to result in a different secret (why?).

The first observation is that the protocol we saw in the previous lecture, being secure against an adversary corrupting at most n/2 parties, is also (passively) secure against an adversary corrupting at most n/3 parties, for obvious reasons. Recall that the protocol consisted of maintaining Shamir shares [x] of degree t for every intermediate result of the computation. For the input values, each party secret-shares its input towards the other parties. The different operations are additions and multiplications. Additions can be handled locally (that is, without communicating) due to the linearity properties of Shamir secret-sharing. On the other hand, multiplications required certain preprocessing material of the form ([r], <r>), where r is some random value unknown to any party, and <.> denotes Shamir secret-sharing with threshold/degree 2t. To multiply two shared values [x] and [y], the parties locally multiplied their shares of each value to get <x*y>, reconstructed <x*y -r> by announcing their shares of this value, and computed locally (x*y -r) + [r] = [x*y]. Finally, when an output value is computed in secret-shared form, the parties reconstruct this to learn the result.

In what follows I will analyze what goes wrong if the parties are actively corrupted. For now, I will assume we have access to the necessary preprocessing material ([r], <r>). Only at the end I will discuss how to generate it with active security.

Input Phase

In the input phase each party is supposed to secret-share its input x towards all parties, to obtain [x]. Recall the share of party Pi corresponding to x should be f(i), where f(X) is a random polynomial of degree at most t subject to f(0)=x. Unfortunately, an actively corrupt party may not distribute correct shares, that is, the resulting shares the parties receive may not be consistent with a polynomial of the right degree (observe that in principle any set of n values is consistent with a polynomial of degree n-1, but being consistent with a polynomial of degree t is a more restrictive requirement). This is a bad way of starting the day! To ensure the resulting shares are consistent, the parties do the following:

1. Preprocess a double-sharing ([r], <r>), and ignore the <.> part (alternatively, when generating this pair only generate the first part),
2. Send the shares of [r] to the party Pi who will provide the input,
3. Pi reconstructs r. Recall that since d=t and t<n/3, Pi succeeds at doing this,
4. Pi broadcasts to all parties the value (x-r), where x is Pi’s input,
5. The parties set their shares to be [x]=[r]+(x-r).

A corrupt Pi may not send the same value (x-r) to all the parties, but instead, it may send different values to different parties. It is easy to see that this would lead the parties to receive potentially inconsistent shares of x, which leaves us right where we started. However, to ensure that Pi cannot do this, the parties make use of a broadcast protocol. These protocols are designed to ensure that all the receivers of some message get the exact same value, and it turns out that if t<n/3, such protocols (with perfect security) exist! Alternatively, you may think of Pi using some kind of “public” medium to disseminate the value (x-r). The point here is that to get consistent sharings the parties only need consistent broadcast, which is much easier to get.

Output Gates

Whenever the parties want to reconstruct some value [z], like the output of the computation for instance, they simply broadcast their shares, and the parties reconstruct the secret from these. Of course, the corrupt parties, being malicious, may broadcast a different share than the one they were supposed to announce. This is where the theory of error detection and correction discussed in the previous lecture comes in handy! As discussed there, if we write n=d+w+1 where d is the degree used for the sharings, then:

1. The adversary can successfully reconstruct an incorrect secret if w<t,
2. The parties can either reconstruct nothing, or be assured that the reconstructed value is correct, if t≤w<2t,
3. The parties can always reconstruct the right value as long as 2t≤w.

For the case of reconstructing [z], the degree is t, so w=n-t-1. Since we are assuming that t<n/3, this implies that 2t≤w, so error correction can be applied to the announced shares of z so that the parties reconstruct the right value regardless of some t potential shares being incorrect.

Multiplication Gates

Addition gates are handled locally via the linearity properties of Shamir secret-sharing. However, for multiplication gates, an interactive protocol is required. Recall that the protocol consists of taking a preprocessed pair ([r],<r>), multiplying locally the given shares of [x] and [y] to obtain <x*y>, reconstructing the value e=<x*y>-<r> and then adding (locally) [x]=e+[r]. When considering an active adversary, the only potential cheating point lies in the reconstruction of e. This involves each party broadcasting its share, and then the parties attempting to interpolate the secret underlying these shares.

To analyze the chance of cheating we again make use of the theory of error detection/correction from the previous lecture. In this case, the goal is to reconstruct a polynomial of degree d=2t. The bound t<n/3 implies this time that w=n-d-1 is at least t, which puts us in the error detection regime. This means that if the parties reconstruct a value they are guaranteed to get the right e, but it might be the case that the shares are no consistent and no value is reconstructed at all. In this case, the parties simply abort and halt the computation, but at least they do not end up computing an incorrect value.

An avid reader who recalls the first lecture may observe that security with abort, which is what is being achieved here, is weaker than the guaranteed output delivery (G.O.D.) property that was promised in the setting where t<n/3. Recall that G.O.D. means that, no matter how badly the adversary deviates from the protocol, the parties are always guaranteed to obtain the final correct output. Although it’s true that in the case of t<n/3, G.O.D. can be achieved, it is not precisely trivial and it requires clever ideas to be able to detect cheaters given that error correction does not work out of the box. A prominent technique to achieve this involves a framework known as player elimination, which involves resolving accusations among the parties so that corrupt parties can be (partially) identified. I know this doesn’t tell you much, and this is deliberate: It is not my intention to consider G.O.D. in these lectures. I would like to refer you to the excellent work of Zuzana Beerliová-Trubíniová and Martin Hirt from TCC 2008, Perfectly-Secure MPC with Linear Communication Complexity.

Offline Phase

So far I have been assuming that the parties had a supply of pairs ([r],<r>), where r is random and unknown to any party. These are independent of the parties’ inputs, and can be computed with enough time in advance before the computation itself begins. The following method I will discuss to precompute these pairs comes from the paper cited above. It makes used of a special type of matrices, which the authors call hyper-invertible matrices, to convert pairs generated locally by each party into general random pairs that can be used for the computation. I discussed a similar construction in the 4th lecture for the honest majority setting, but this was with passive security only.

Hyper-Invertible Matrices

A matrix is hyper-invertible is every non-trivial square sub-matrix is invertible. The most useful consequence of this property for our purposes is the following: Consider a n-times-n hyper-invertible matrix M, and let x and y be n-dimensional vectors such that y=Mx. Choose any p entries of x, and any q entries of y, with p+q=n. Then, there exists a 1–1 mapping between these entries, and the remaining entries of each of x and y. To illustrate why this holds, assume that n is even and that p=q=n/2, and that the selected entries of x are the first n/2 and these of y are the last n/2. We can partition M in four n/2-times-n/2 blocks M11, M12, M21, M22. This way, if we split x by half as (x1,x2) and y as (y1,y2), then it holds that

Since M is hyper-invertible, the submatrices M11 and M22 are invertible. It is left as an exercise to show that this, together with the equations above, shows that any choice of the selected entries (x1,y2) can be mapped in a 1–1 manner to the entries (x2,y1).

Hyper-invertible matrices do exist, and here is an example of one, whose properties you are encouraged to verify: Let the i,j entry be given by

where the b’s and a’s are all just different values in the given field. The reason why this yields a hyper-invertible matrix is related to the fact that these entries form Lagrange interpolation coefficients, which provide an alternative view to the interpolation theorems I discussed in the lecture about Shamir secret-sharing.

Preprocessing Pairs ([r],<r>)

The goal now is to make use of a n-times-n hyper-invertible matrix M in order to preprocess a pair ([r],<r>) efficiently. In fact, multiple such pairs will be produced by the protocol that will be presented below.

1. Each party Pi samples a random ri and secret-shares it with degree t and 2t, which yields ([ri],<ri>). Observe that a corrupt party may completely deviate from this step and may end up sharing inconsistent values!
2. The parties take the vectors of shares ([r1],…,[rn]) and (<r1>,…,<rn>) and multiply them by M, obtaining ([s1],…,[sn]) and (<s1>,…,<sn>). Observe that this is a linear operation so it can be done locally by each party operating on its own shares.
3. For each i=1,…,2t, the parties send their shares of [si] and <si> to Pi.
4. Pi tries to reconstruct these shares and verifies if (1) reconstruction succeeds and (2) the two reconstructed values with the two degrees coincide. If this is not the case, then Pi broadcasts a “complain” signal to all the other parties. Observe that a corrupt party may observe inconsistencies but not report it nevertheless.
5. If no party complains in the previous step, then the parties output the pairs ([si],<si>) for i=2t+1,…,n as valid preprocessing material. Otherwise, the parties simply abort.

We have to argue two things about the protocol above. First, we need to show that if the protocol does not result in abort, then the parties end up producing valid double-shares ([s],<s>), meaning by “valid” that they are consistent with polynomials of the right degrees t and 2t, and the underlying secrets are the same. Second, we need to prove that the underlying secret s is random and unknown to the adversary. Both of these can be proven using the properties of hyper-invertible matrices. For the first property, suppose that no party among P1,…,P_2t complains in the fourth step above. Among these parties, t of them may be corrupt, and for concreteness let us assume these are P1,…,Pt. Since the remaining t honest parties P_t+1,…,P_2t did not complain, this means that the shares ([si],<si>) for i=t+1,…,2t that these parties received were indeed correct. Additionally, the original shares ([ri],<ri>) distributed by the honest parties, that is, for i=t+1,…,n, are by assumption correct. We see then that there are t pairs among the output of M that are correct, and n-t pairs among the input that are correct. These two numbers add up to n, so by the properties of M discussed above, the remaining entries of the input and the output can be written as a linear combination of the correct entries. In particular, the returned shares ([si],<si>) for i=2t+1,…,n are a linear combination of “correct” shares and therefore they are correct as well.

The second property, privacy towards the adversary, is proved in a similar way, and it’s mostly left as an exercise. As a hint, try to write ([si],<si>) for i=2t+1,…,n as a 1–1 affine transformation of the honest shares ([ri],<ri>) for i=2t+1,…,n; since the latter look uniformly random and unknown to the adversary, the shares after this transformation also inherit this property.

I’m truly sorry if I lost you by describing this method to generate double-sharings! It is highly non-trivial and, additionally, I think it is not fully necessary to understand it completely to get a general idea of how the MPC protocol for active security with t<n/3 works. The main takeaway of this post should be that, assuming preprocessing is given “for free”, there is a simple actively secure protocol with perfect security assuming at most t<n/3 corruptions, which only makes uses of error correction and detection to ensure correct behavior. The preprocessing can be instantiated using hyper-invertible matrices, which are matrices for which each square submatrix is invertible.

Finally, I encourage you to try to think a little bit about what breaks in the protocol described here if we assume t<n/2 instead of t<n/3. Something has to break, given that a perfectly secure protocol in an honest majority setting with active security cannot exist. This thought process will be useful later on, when we discuss how to extend the general idea of the protocol described here from t<n/3 to t<n/2.