# 17.2 Threshold Schemes

In the previous section, we showed how to split a secret among  people so that all  were needed in order to reconstruct the secret. In this section we present methods that allow a subset of the people to reconstruct the secret.

It has been reported that the control of nuclear weapons in Russia employed a safety mechanism where two out of three important people were needed in order to launch missiles. This idea is not uncommon. It’s in fact a plot device that is often employed in spy movies. One can imagine a control panel with three slots for keys and the missile launch protocol requiring that two of the three keys be inserted and turned at the same time in order to launch missiles to eradicate the earth.

Why not just use the secret splitting scheme of the previous section? Suppose some country is about to attack the enemy of the week, and the secret is split among three officials. A secret splitting method would need all three in order to reconstruct the key needed for the launch codes. This might not be possible; one of the three might be away on a diplomatic mission making peace with the previous week’s opponent or might simply refuse because of a difference of opinion.

# Definition

Let  be positive integers with . A -threshold scheme is a method of sharing a message  among a set of  participants such that any subset consisting of  participants can reconstruct the message , but no subset of smaller size can reconstruct .

The -threshold schemes are key building blocks for more general sharing schemes, some of which will be explored in the Exercises for this chapter. We will describe two methods for constructing a -threshold scheme.

The first method was invented in 1979 by Shamir and is known as the Shamir threshold scheme or the Lagrange interpolation scheme. It is based upon some natural extensions of ideas that we learned in high school algebra, namely that two points are needed to determine a line, three points to determine a quadratic, and so on.

Choose a prime , which must be larger than all possible messages and also larger than the number  of participants. All computations will be carried out mod . The prime replaces the integer  of Section 17.1. If a composite number were to be used instead, the matrices we obtain might not have inverses.

The message  is represented as a number mod , and we want to split it among  people in such a way that  of them are needed to reconstruct the message. The first thing we do is randomly select  integers mod ; call them . Then the polynomial



is a polynomial such that . Now, for the  participants, we select distinct integers  and give each person a pair  with . For example,  is a reasonable choice for the ’s, so we give out the pairs , one to each person. The prime  is known to all, but the polynomial  is kept secret.

Now suppose  people get together and share their pairs. For simplicity of notation, we assume the pairs are . They want to recover the message .

We begin with a linear system approach. Suppose we have a polynomial  of degree  that we would like to reconstruct from the points , where . This means that



If we denote , then we may rewrite this as



The matrix, let’s call it , is what is known as a Vandermonde matrix. We know that this system has a unique solution mod  if the determinant of the matrix  is nonzero mod  (see Section 3.8). It can be shown that the determinant is



which is zero mod  only when two of the ’s coincide mod  (this is where we need  to be prime; see Exercise 13(a) in Chapter 3). Thus, as long as we have distinct ’s, the system has a unique solution.

We now describe an alternative approach that leads to a formula for the reconstruction of the polynomial and hence for the secret message. Our goal is to reconstruct a polynomial  given that we know  of its values . First, let



Here, we work with fractions mod  as described in Section 3.3. Then



This is because  is a product of factors , all of which are 1. When , the product for  contains the factor , which is 0.

The Lagrange interpolation polynomial



satisfies the requirement  for . For example,



We know from the previous approach with the Vandermonde matrix that the polynomial  is the only one of degree  that takes on the specified values. Therefore, .

Now, to reconstruct the secret message all we have to do is calculate  and evaluate it at . This gives us the formula



# Example

Let’s construct a -threshold scheme. We have eight people and we want any three to be able to determine the secret, while two people cannot determine any information about the message.

Suppose the secret is the number  (which corresponds to the word secret). Choose a prime , for example,  (we need a prime at least as large as the secret, but there is no advantage in using primes much larger than the maximum size of the secret). Choose random numbers  and  mod  and form the polynomial



For example, let’s work with



We now give the eight people pairs . There is no need to choose the values of  randomly, so we simply use . Therefore, we distribute the following pairs, one to each person:



Suppose persons 2, 3, and 7 want to collaborate to determine the secret. Let’s use the Lagrange interpolating polynomial. They calculate that the following polynomial passes through their three points:



At this point they realize that they should have been working mod . But



so they replace 1/5 by , as in Section 3.3, and reduce mod  to obtain



This is, of course, the original polynomial . All they care about is the constant term 190503180520, which is the secret. (The last part of the preceding calculations could have been shortened slightly, since they only needed the constant term, not the whole polynomial.)

Similarly, any three people could reconstruct the polynomial and obtain the secret.

If persons 2, 3, and 7 chose the linear system approach instead, they would need to solve the following:



This yields



so they again recover the polynomial and the message.

What happens if only two people get together? Do they obtain any information? For example, suppose that person 4 and person 6 share their points (4, 442615222255) and (6, 852136050573) with each other. Let  be any possible secret. There is a unique quadratic polynomial  passing through the points , (4, 442615222255), and (6, 852136050573). Therefore, any secret can still occur.

Similarly, they cannot guess the share held, for example, by person 7: Any point  yields a unique secret , and any secret  yields a polynomial , which corresponds to . Therefore, every value of  can occur, and each corresponds to a secret. So persons 4 and 6 don’t obtain any additional information about which secrets are more likely when they have only their own two points.

Similarly, if we use a polynomial of degree , there is no way that  persons can obtain information about the message with only their data. Therefore,  people are required to obtain the message.

For another example, see Example 38 in the Computer Appendices.

There are other methods that can be used for secret sharing. We now describe one due to Blakley, also from 1979. Suppose there are several people and we want to arrange that any three can find the secret, but no two can. Choose a prime  and let  be the secret. Choose  randomly mod . We therefore have a point  in three-dimensional space mod . Each person is given the equation of a plane passing through . This is accomplished as follows. Choose  randomly mod  and then set . The plane is then



This is done for each person. Usually, three planes will intersect in a point, which must be . Two planes will intersect in a line, so usually no information can obtained concerning the secret  (but see Exercise 13).

Note that only one coordinate should be used to carry the secret. If the secret had instead been distributed among all three coordinates , then there might be only one meaningful message corresponding to a point on a line that is the intersection of two persons’ planes.

The three persons who want to deduce the secret can proceed as follows. They have three equations



which yield the matrix equation



As long as the determinant of this matrix is nonzero mod , the matrix can be inverted mod  and the secret  can be found (of course, in practice, one would tend to solve this by row operations rather than by inverting the matrix).

# Example

Let . Suppose we give A, B, C, D, E the following planes:



If A, B, C want to recover the secret, they solve



The solution is , so the secret is . Similarly, any three of A, B, C, D, E can cooperate to recover .

By using -dimensional hyperplanes in -dimensional space, we can use the same method to create a -threshold scheme for any values of  and .

As long as  is reasonably large, it is very likely that the matrix is invertible, though this is not guaranteed. It would not be hard to arrange ways to choose  so that the matrix is always invertible. Essentially, this is what happens in the Shamir method. The matrix equations for both methods are similar, and the Shamir method could be regarded as a special case of the Blakley method. But since the Shamir method yields a Vandermonde matrix, the equations can always be solved. The other advantage of the Shamir method is that it requires less information to be carried by each person:  versus .

We now return to the Shamir method and consider variations of the basic situation. By giving certain persons more shares, it is possible to make some people more important than others. For example, suppose we have a system in which eight shares are required to obtain the secret, and suppose the boss is given four shares, her daughters are given two shares, and the other employees are each given one share. Then the boss and two of her daughters can obtain the secret, or three daughters and two regular employees, for example.

Here is a more complicated situation. Suppose two companies A and B share a bank vault. They want a system where four employees from A and three from B are needed in order to obtain the secret combination. Clearly it won’t work if we simply supply shares that are all for the same secret, since one company could simply use enough partial secrets from its employees that the other company’s shares would not be needed. The following is a solution that works. Write the secret  as the sum of two numbers . Now make  into a secret shared among the employees of A as the constant term of a polynomial of degree 3. Similarly, let  be the constant term of a polynomial of degree 2 and use this to distribute shares of  among the employees of B. If four employees of A and three employees of B get together, then those from A determine  and those from B determine . Then they add  and  to get .

Note that  does not obtain any information about the secret  by itself since  has a unique solution  for every , so every possible value of  corresponds to a possible value of . Therefore, knowing  does not help  to find the secret;  also needs to know .