MPC Techniques Series, Part 3: Secret Sharing Shamir Style

By Ivan Damgård, Professor and Chief Cryptographer at Partisia

One of the main tools offered by modern crypto and multiparty computation (MPC) in particular is secret-sharing. This concept was explained in a previous blog post on Secret Sharing. To recap:

A so-called dealer has a secret number s. She does some computation involving various random choices and produces an output as a set of n shares s1,…,sn. The idea is that you can distribute these shares (privately on a secure connection) to n parties. It turns out that this will be a very robust way to store s because it gives you some assurance that s will remain secret, but also that s will not be lost.

This is because the shares are constructed with respect to a threshold value t, a number between 1 and n. The idea is that given any t shares or less, you will learn nothing at all about s, but given at least t+1 shares, you can easily compute s. So, this means that if at most t of the n shareholders are corrupt and leak their shares, your secret is safe, but as long as at least t+1 of them are alive and do the right thing, your secret will not be lost.

Adi Shamir (who is also the S in RSA) invented an elegant way to do secret-sharing for any n and t. We will look at a graphical way to explain what he did. Let us assume n=4 and t=1, so the goal is that 1 share would not result in information being leaked, however, any 2 would be enough to result in a leak. See below an x-axis and a y-axis as you used to do in school when drawing graphs. On the graph, we have assigned x-coordinates 1,2,3 and 4 to the 4 participants. When the dealer wants to share a secret s, she thinks of the secret number s as a y-coordinate and draws a random line that passes through the point (0,s). The shares are now defined as points on this line (see fig 1). For instance, participant number 3 gets a number s3, such that (3,s3) is on the line.

Now, consider your situation if you were given only 1 share. You have only one point and no idea which line the dealer chose, except that it passes through your point. This also means you have no idea where it intersects the y-axis. Any guess at the intersection point would define a line which is just as likely as any other line, see fig. 2.

However, if you are given 2 points, you can draw the correct line, and compute the intersection with the y-axis.

Note that each party gets only a single number as his share, so shares are the same size as the secret. This is the most compact scheme possible, also known as an ideal secret-sharing.

Of course, there is nothing special about n=4, we can do the same for any n. What about values of t that are greater than 1? Well, you may remember from school that the idea that a certain number of points determine a curve is more general than just “any 2 points determine a line”. For a degree 2 curve, a parabola, we need exactly 3 points to determine it. So to share with t=2, the dealer would draw a random parabola intersecting the y-axis in (0,s). In general, you need t+1 points to determine a degree-t curve. This is the idea of the general scheme, but we will not explore it further here.

Secret-Sharing and MPC
What does all this have to do with MPC, you ask? Everything, actually! Once values have been secret-shared, we can perform computation on them while they are shared. For example, addition is quite easy. Have a look at fig. 3. It shows two values a and b that have been shared. Now, assume we ask all parties to add the two shares they have, of a and b, respectively. It turns out that the resulting points will be on a line intersecting the y-axis in the point (0,a+b). So we have created a situation that is exactly as if a+b had been shared in the first place. Thus, if parties were to make the new shares public, this would reveal a+b but no other information on a and b.

Doing multiplications is a bit more complicated but can be done using ideas similar to those explained in Claudio’s post: each participant does a local multiplication and secret-shares the result. Then players add all the shares they receive.

Dealing with malicious parties
In many cases it is not realistic to assume that all parties will follow instructions. What if some of them do not? Can we still get correct results? This is known as security against an active adversary. As an example, let’s assume that we have done the addition of two secret-shared values a and b. We now want to learn the result, but (at most) one of our 4 participants is malicious and will not follow the specified protocol.

Now, if the parties try to reconstruct the result a+b by making their shares public, the problem is that one party may send an incorrect value, and we do not know in advance which one. However, have a look at fig. 4, that contains an example of the shares that might be sent. Considering the fact that IF everyone had been honest, all shares would be on a line, I’m sure you will agree that it is quite easy to see which share is incorrect and what the value should have been.

This phenomenon is very general: it turns out that as long as t is less than n/3 and at most t players lie about their shares, we can use a method called error correction to determine which shares are incorrect, and therefore still compute the correct secret.

If you have been paying close attention, you may have noticed that I cheated a bit: the error correction sketched here only works if all the honest players are on the same line, and this is only the case if the dealer (or dealers) who sent out shares followed instructions. So, what should we do if the dealer is malicious? Fortunately, protocols exist for so-called Verifiable Secret-Sharing (VSS), where the dealer not only sends out shares but also convinces everyone that he did the right thing, without revealing the secret. For instance, in the case of t=1, all shares must be on the same line. Like error correction, VSS can be made to work with no probability of error, if t is less than n/3.

With these ingredients, we are in a position to explain one of the crucial results in MPC: Any function can be computed securely with no probability of error, as long as the involved parties have secure channels for communication and less than one third of them are malicious. The parties supply input by using VSS to reliably share the inputs, we then do the desired computation on the shares, and in the end the parties hold shares of the desired output. Finally, the parties reveal the shares of the output using error correction to deal with incorrect shares. This reveals the output and nothing else.

Finally, I have a confession: in order to be able to show you drawings of Shamir’s scheme, I had to assume that we work with real numbers as secrets and shares. But this is never done in real life: on real computers we can only do limited precision for real numbers and this ruins security. What we do instead is the same thing, but we replace computation on the reals by computation modulo a prime number. For instance, using the prime 7, we would replace the reals by the set {0,1,…,6}, and now 4+5 is no longer 9, but is 4+5 mod 7= 2. In a nutshell, everything happening in the graphs above can be written down as algebraic formulas, and we then interpret these as formulas for computation modulo a prime number.

About the author
Ivan is professor and head of the research group in cryptography at Aarhus University. Ivan is co-founder of Cryptomathic, Partisia and Sepior. He is one of the top cited and publishing researchers in cryptography, is a fellow of the IACR (International Association for Cryptologic Research), and received the 2015 RSA Award for Excellence in the Field of Mathematics.