A Crash Course on MPC, Part 3
Shamir Secret-Sharing
Welcome to the third proper lecture on MPC. In the last post, I showed you the sketch of a protocol that two parties, Alejandra and Bonifacio, could use to securely compute any function defined by additions and multiplications over some field. The core tool we used there was additive secret sharing. This is a ‘secret’ representation of the data that does not allow either party to learn the underlying values, but allows computation on these nevertheless. The goal of this section is to generalize this idea, and present a construction that works for any number of parties, and any threshold (recall this is the number that dictates how many parties the adversary is allowed to corrupt).
Linear Secret-Sharing Schemes
The concrete objects of interest to us are (threshold) linear secret-sharing schemes. These are parameterized by two values (t, n), and their purpose is to split a value x into n values, known as shares, in such a way that (1) at most t of any of these shares together leak nothing about the secret value x, but any t+1 shares together completely define the secret. On top of this there is a linearity property: Given shares (x1, …, xn) and (y1, …, yn) of some values x and y, the values (x1+y1, …, xn+yn) are shares of x+y. All these operations happen over some algebraic structure, let’s say for our purposes that it is modulo some prime p, so the algebraic structure is a field. Recall that a field is simply a set in which you have ‘compatible’ addition, subtraction and multiplication operations, and also division when the divisor is not zero.
We already saw an example of a linear secret-sharing scheme for n=2 and t=1: To secret-share a value x, sample one of the shares at random, say x2, and set the other share x1 as x-x2. This naturally generalizes to any n, as long as t=n-1: Sample n-1 shares at random, say x2, x3, …, xn, and set the remaining share x1 as x-x2-x3-…-xn. In what follows you will learn about Shamir secret-sharing, which is a very popular linear secret-sharing scheme that works for any n and any t<n.
Shamir Secret-Sharing
I believe this is the most math-heavy part in any of the posts in this series, so please bear with me. Underlying Shamir secret-sharing lies the theory of polynomial interpolation, which I explain below.
Polynomial Interpolation
As I mentioned before, the algebraic structure I will consider from now on are finite fields. An example of a field is the set of real numbers, but this is not finite. An example of a finite field is the set of integers modulo a prime; these are known as prime fields. There are also other types of finite fields known as extension fields, but I will ignore these here. In what follows, let F be the finite field of integers modulo p, with p a prime larger than n.
Consider a polynomial of degree at most t, f(X) = a0+a1*X¹+…+at*X^t, where the coefficients lie in F. Because p is larger than n, the numbers 0, 1, 2, …, n are different elements in F. Now imagine you evaluate these points into the polynomial f(X), you would get the values f(0), f(1), …, f(n). The question now is: How ‘independent’ are these values?
Any set of t+1 evaluation points completely define the polynomial f, and therefore, they also define the remaining evaluation points. The best way to show this, I think, is using linear algebra. Consider t+1 different values i0, i0, …, it. We have the following simple relation:
Now, the (t+1)x(t+1) matrix that appears in the expression above is called a Vandermonde matrix, and it can be shown to be invertible as long as (in fact, if and only if) all the points i0, …, it are different, which is the case here. This shows that the polynomial f(X), given by the coefficients a0, a1, …, at, is completely determined by the values f(i0), …, f(it). Furthermore, and this is left as an exercise for you (which can be easily proven using what I just stated above), given any other t+1 points j0, j1, …, jt, there exists an invertible matrix A such that
Distributing a Secret
Let’s discuss now how to turn the ideas presented above to distribute a secret. Let s be the value we want to distribute among the n parties P1, …, Pn. Sample t random values a1, …, at, and let a0 = s. Consider the polynomial f(X) = a0+a1*X¹+…+at*X^t, which is a random polynomial of degree at most t subject to f(0) = s. Distribute to party Pi the share f(i), that is, the shares are (f(1), …, f(n)). This is the famous Shamir secret-sharing scheme.
We have to verify now that this satisfies the conditions of a linear secret-sharing scheme. The first matrix relation above shows that, given t shares, and given any potential secret s’, one can always find a polynomial that is consistent with this secret and with the t shares, which shows that these shares do not leak anything about the secret since any secret is possible.
The same matrix relation shows that t+1 shares together completely determine the polynomial, and in particular, they determine the secret. Furthermore, one can use the second matrix relation allows us to be a bit more explicit: Given any set of t+1 parties with indexes i0, …, it, there exist coefficients c0, …, ct (that depend on this set) such that s = c0*f(i0)+ … +ct*f(it), that is, the secret is obtained as a linear combination of the shares of these parties! If you want to be even more explicit with respect to how these coefficients look like, you could get an explicit description of the matrix A from the previous subsection, or alternatively, search for Lagrange coefficients. Finally, linearity is left as an exercise.
Notes
- Note that for t=n-1, Shamir secret-sharing becomes essentially the additive secret-sharing scheme discussed at the beginning of this post. To see this, recall that given the t+1 = n shares f(1), …, f(n), there exist coefficients c1, …, cn such that the secret is computed as s = c1*f(1)+ … + cn*f(n). If each party Pi define its share to be ci*f(i), these become additive shares.
- If you are somewhat familiar with coding theory, you will find Shamir secret sharing very similar to Reed-Solomon error correction. Indeed, this is the case, and the observation is more general than that: There is a one-to-one correspondence between linear error correcting codes and linear secret-sharing schemes. Intuitively, this should make sense as in error correcting codes one is interested in reconstructing messages from only certain symbols of a codeword, which is similar to the task of reconstructing a secret from a subset of the shares.
- Shamir secret-sharing also works over other algebraic structures, not only fields, as long as one is able to find n+1 points such that the pairwise differences of these are invertible.
