A Crash Course on MPC, Part 5
Error Detection and Error Correction
In the previous lecture I discussed a protocol for honest-majority MPC (that is, t<n/2) that achieves perfect security under the presence of a semi-honest adversary, that is, one that follows the protocol specification faithfully. The goal of this post is to pave the way towards active security.
There are multiple things that break in the protocol from the previous lecture when facing an active adversary, but among all things, a critical one is cheating at reconstruction time. Opening, or reconstructing a value that is secret-shared is an essential operation. In our protocol, it is used a couple of times: To reconstruct <x*y-r> in the multiplication gates, and of course, to learn the result of the computation. Hence, it becomes essential to determine whether an actively corrupt party can disrupt the reconstruction of some shared value by lying about its own share. More precisely, suppose that a value s is Shamir secret-shared using a polynomial of degree at most d, that is, each party Pi gets si=f(i), where f(X) is a random polynomial of degree at most d such that f(0)=s. When reconstructing this value, a corrupt party can announce some si’ instead of the correct si. The question that appears is then, what would the parties end up reconstructing?
One thing is for sure: If the parties only use d+1 of the announced shares to reconstruct the secret (at the end, recall that only d+1 shares are necessary), then the adversary can make the parties reconstruct a different secret. This is because any d+1 shares are always consistent with a polynomial of degree at most d, so given only d+1 shares there is no way to know if there were incorrect shares among the set. However, imagine that the parties use d+2 shares to reconstruct, or, more precisely, they use d+1 shares but then verify that the interpolated polynomial is consistent with the extra share. Intuitively, the parties can be more confident that they are reconstructing the right value if more shares than the necessary ones (d+1) happen to be consistent with the reconstructed polynomial. Now the question is whether only one extra consistent share is enough, which is what I explore next.
Recall that there are t corrupted parties, so potentially there are t announced shares si’ that are incorrect. Write n=d+w+1. Assume that the parties reconstruct the polynomial using the first d+1 shares, and then check that the remaining w shares are consistent with this polynomial as well. First assume that w<t, I would like to prove that in this case the adversary can still make the n shares look consistent with a polynomial of degree at most d, but with a different secret. To see why this is the case, consider a non-zero value e chosen by the adversary, and let g(X) be a polynomial of degree at most d such that g(0)=e and g(i)=0 for each honest party Pi. Notice that there are n-t honest parties, which is smaller than n-w=d+1, so such polynomial indeed exists. The corrupt parties can announce the share si’ = si+g(i), and the honest parties would still announce si = si+g(i). All the resulting shares are consistent with the polynomial f(X)+g(X), but now the secret reconstructed is s+e, rather than s.
Error Detection
We saw that if w<t then the consistency from the w extra shares does not really help the parties in concluding that they reconstructed the right value. However, it turns out that, if w≥t, then this consistency is enough! That is, if d+w+1 shares are consistent with a polynomial of degree at most d, with w≥t, then the parties can be confident that the reconstructed secret is the right one. The reason for this is actually very simple: If d+w+1 shares are consistent, in particular, the (d+w+1)-t≥d+1 shares from the honest parties are also consistent, however, these are enough to determine the polynomial on their own, so the reconstructed polynomial must be the same than the one the honest parties would have reconstructed by themselves, so the secret is indeed the correct one.
This property is called error detection, and it is a term borrowed from the coding theory literature. In a nutshell, if w≥t, the parties are able to detect whether or not there are errors on the shares, and only reconstruct the right secret. Observe, however, that the parties are not able to tell what the wrong shares are.
Error Correction
So far, we have seen that if w≥t, then the parties only reconstruct the right secret, but it may still be the case that they reconstruct nothing if some errors are detected. It turns out that if w≥2t, then the parties can go further and not only detect whether there are errors, but actually find them, remove them, and reconstruct the right secret. This is very useful when considering notions like guaranteed output delivery, where we want the parties to obtain output, no matter what the adversary does. I will not prove the property above, but I will motivate why it holds. Imagine that, from the announced shares, the parties are able to find a subset of size n-t that is consistent with a polynomial of degree at most d. Notice that such subset exists, namely, the one corresponding to the honest shares. Unfortunately, the parties cannot conclude that this subset corresponds to that of the honest shares, given that it may be the case that some corrupt shares were consistent “coincidentally”. However, what they do know is that they have a set of n-t≥n+(t-w)≥d+t+1 consistent shares, and as before, this is enough to conclude that the secret they reconstruct to is correct as it can be obtained from the honest parties’ shares only.
The challenge with the sketch above lies in finding the consistent subset of size n-t, since there are exponentially many subsets of that size and exhaustive search would not be feasible. Here is where the theory of error-correction kicks in: There exists a (non-trivial!) efficient error correction algorithm that finds this subset in polynomial time.
In summary, we saw that if the degree of the polynomial used for the sharing is at most d, and if w=n-d-1, then:
- The adversary can successfully reconstruct an incorrect secret if w<t,
- The parties can either reconstruct nothing, or be assured that the reconstructed value is correct, if t≤w<2t,
- The parties can always reconstruct the right value as long as 2t≤w.
We will exploit these properties in subsequent lectures to enable MPC with active security.
