In the previous section, we showed how to split a secret among $m$ people so that all $m$ 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.

The $(t\text{,}w)$-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 $(t\text{,}w)$-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 $p$, which must be larger than all possible messages and also larger than the number $w$ of participants. All computations will be carried out mod $p$. The prime replaces the integer $n$ of Section 17.1. If a composite number were to be used instead, the matrices we obtain might not have inverses.

The message $M$ is represented as a number mod $p$, and we want to split it among $w$ people in such a way that $t$ of them are needed to reconstruct the message. The first thing we do is randomly select $t-1$ integers mod $p$; call them $s_1\text{,}{s}_2\text{,}\cdots s_{t-1}$. Then the polynomial

is a polynomial such that $s(0)\equiv M(\text{mod}p)$. Now, for the $w$ participants, we select distinct integers $x_1\text{,}\dots \text{,}{x}_w(\text{mod}p)$ and give each person a pair $(x_i\text{,}{y}_i)$ with $y_i\equiv s(x_i)(\text{mod}p)$. For example, $1\text{,}2\text{,}\dots \text{,}w$ is a reasonable choice for the $x$’s, so we give out the pairs $(1\text{,}s(1))\text{,}\dots \text{,}(w\text{,}s(w))$, one to each person. The prime $p$ is known to all, but the polynomial $s(x)$ is kept secret.

Now suppose $t$ people get together and share their pairs. For simplicity of notation, we assume the pairs are $(x_1\text{,}{y}_1)\text{,}\cdots \text{,}(x_t\text{,}{y}_t)$. They want to recover the message $M$.

We begin with a linear system approach. Suppose we have a polynomial $s(x)$ of degree $t-1$ that we would like to reconstruct from the points $(x_1\text{,}{y}_1)\text{,}\cdots \text{,}(x_t\text{,}{y}_t)$, where $y_k=s(x_k)$. This means that

If we denote $s_0=M$, then we may rewrite this as

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

which is zero mod $p$ only when two of the $x_i$’s coincide mod $p$ (this is where we need $p$ to be prime; see Exercise 13(a) in Chapter 3). Thus, as long as we have distinct $x_k$’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 $s(x)$ given that we know $t$ of its values $(x_k\text{,}{y}_k)$. First, let

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

This is because $l_k(x_k)$ is a product of factors $(x_k-x_i)/(x_k-x_i)$, all of which are 1. When $k\ne j$, the product for $l_k(x_j)$ contains the factor $(x_j-x_j)/(x_k-x_j)$, which is 0.

The Lagrange interpolation polynomial

satisfies the requirement $p(x_j)=y_j$ for $1\le j\le t$. For example,

We know from the previous approach with the Vandermonde matrix that the polynomial $s(x)$ is the only one of degree $t-1$ that takes on the specified values. Therefore, $p(x)=s(x)$.

Now, to reconstruct the secret message all we have to do is calculate $p(x)$ and evaluate it at $x=0$. This gives us the formula

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 $p$ and let $x_0$ be the secret. Choose $y_0\text{,}{z}_0$ randomly mod $p$. We therefore have a point $Q=(x_0\text{,}{y}_0\text{,}{z}_0)$ in three-dimensional space mod $p$. Each person is given the equation of a plane passing through $Q$. This is accomplished as follows. Choose $a\text{,}b$ randomly mod $p$ and then set $c\equiv z_0-a{x}_0-b{y}_0(\text{mod}p)$. The plane is then

This is done for each person. Usually, three planes will intersect in a point, which must be $Q$. Two planes will intersect in a line, so usually no information can obtained concerning the secret $x_0$ (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 $x_0\text{,}{y}_0\text{,}{z}_0$, 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 $p$, the matrix can be inverted mod $p$ and the secret $x_0$ can be found (of course, in practice, one would tend to solve this by row operations rather than by inverting the matrix).

By using $(t-1)$-dimensional hyperplanes in $t$-dimensional space, we can use the same method to create a $(t\text{,}w)$-threshold scheme for any values of $t$ and $w$.

As long as $p$ 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 $a\text{,}b\text{,}c$ 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: $(x\text{,}y)$ versus $(a\text{,}b\text{,}c\text{,}\dots )$.

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 $s$ as the sum of two numbers $s\equiv c_A+c_B(\text{mod}p)$. Now make $c_A$ into a secret shared among the employees of A as the constant term of a polynomial of degree 3. Similarly, let $c_B$ be the constant term of a polynomial of degree 2 and use this to distribute shares of $c_B$ among the employees of B. If four employees of A and three employees of B get together, then those from A determine $c_A$ and those from B determine $c_B$. Then they add $c_A$ and $c_B$ to get $s$.

Note that $A$ does not obtain any information about the secret $s$ by itself since $c_A+x\equiv s(\text{mod}p)$ has a unique solution $x$ for every $s$, so every possible value of $s$ corresponds to a possible value of $c_B$. Therefore, knowing $c_A$ does not help $A$ to find the secret; $A$ also needs to know $c_B$.