# 17.2 Threshold Schemes

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.

# Definition

Let $t\text{,}\text{}w$ be positive integers with $t\le w$. A $\mathbf{(}t\text{,}\text{}w)$**-threshold scheme** is a method of sharing a message $M$ among a set of $w$ participants such that any subset consisting of $t$ participants can reconstruct the message $M$, but no subset of smaller size can reconstruct $M$.

The $(t\text{,}\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{,}\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{,}\text{}{s}_{2}\text{,}\text{}\cdots \text{}{s}_{t-1}$. Then the polynomial

is a polynomial such that $s(0)\equiv M\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)$. Now, for the $w$ participants, we select distinct integers ${x}_{1}\text{,}\text{}\dots \text{,}\text{}{x}_{w}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)$ and give each person a pair $({x}_{i}\text{,}\text{}{y}_{i})$ with ${y}_{i}\equiv s({x}_{i})\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}p)$. For example, $1\text{,}\text{}2\text{,}\text{}\dots \text{,}\text{}w$ is a reasonable choice for the $x$’s, so we give out the pairs $(1\text{,}\text{}s(1))\text{,}\text{}\dots \text{,}\text{}(w\text{,}\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{,}\text{}{y}_{1})\text{,}\text{}\cdots \text{,}\text{}({x}_{t}\text{,}\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{,}\text{}{y}_{1})\text{,}\text{}\cdots \text{,}\text{}({x}_{t}\text{,}\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{,}\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

# Example

Let’s construct a $(3\text{,}\text{}8)$-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 $M=190503180520$ (which corresponds to the word *secret*). Choose a prime $p$, for example, $p=1234567890133$ (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 ${s}_{1}$ and ${s}_{2}$ mod $p$ and form the polynomial

For example, let’s work with

We now give the eight people pairs $(x\text{,}\text{}s(x))$. There is no need to choose the values of $x$ randomly, so we simply use $x=1\text{,}\text{}2\text{,}\text{}\dots \text{,}\text{}8$. 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 $p$. But

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

This is, of course, the original polynomial $s(x)$. 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 $c$ be any possible secret. There is a unique quadratic polynomial $a{x}^{2}+bx+c$ passing through the points $(0\text{,}\text{}c)$, (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 $(7\text{,}\text{}{y}_{7})$ yields a unique secret $c$, and any secret $c$ yields a polynomial $a{x}^{2}+bx+c$, which corresponds to ${y}_{7}=49a+7b+c$. Therefore, every value of ${y}_{7}$ 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 $t-1$, there is no way that $t-1$ persons can obtain information about the message with only their data. Therefore, $t$ 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 $p$ and let ${x}_{0}$ be the secret. Choose ${y}_{0}\text{,}\text{}{z}_{0}$ randomly mod $p$. We therefore have a point $Q=({x}_{0}\text{,}\text{}{y}_{0}\text{,}\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{,}\text{}b$ randomly mod $p$ and then set $c\equiv {z}_{0}-a{x}_{0}-b{y}_{0}\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}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{,}\text{}{y}_{0}\text{,}\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).

# Example

Let $p=73$. 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 $({x}_{0}\text{,}\text{}{y}_{0}\text{,}\text{}{z}_{0})=(42\text{,}\text{}29\text{,}\text{}57)$, so the secret is ${x}_{0}=42$. Similarly, any three of A, B, C, D, E can cooperate to recover ${x}_{0}$.

By using $(t\phantom{\rule{negativethinmathspace}{0ex}}-\phantom{\rule{negativethinmathspace}{0ex}}1)$-dimensional hyperplanes in $t$-dimensional space, we can use the same method to create a $(t\text{,}\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{,}\text{}b\text{,}\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{,}\text{}y)$ versus $(a\text{,}\text{}b\text{,}\text{}c\text{,}\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{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}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{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}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}$.