17.2 Threshold Schemes – Introduction to Cryptography with Coding Theory, 3rd Edition

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, w be positive integers with tw. A (t, 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, 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, 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 t1 integers mod p; call them s1, s2,  st1. Then the polynomial

s(x)M+s1x++st1xt1(modp)

is a polynomial such that s(0)M(modp). Now, for the w participants, we select distinct integers x1, , xw(modp) and give each person a pair (xi, yi) with yis(xi)(modp). For example, 1, 2, , w is a reasonable choice for the x’s, so we give out the pairs (1, s(1)), , (w, 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 (x1, y1), , (xt, yt). They want to recover the message M.

We begin with a linear system approach. Suppose we have a polynomial s(x) of degree t1 that we would like to reconstruct from the points (x1, y1), , (xt, yt), where yk=s(xk). This means that

ykM+s1xk1++st1xkt1(modp), 1kt.

If we denote s0=M, then we may rewrite this as

1x1x1t11x2x2t11xtxtt1s0s1st1y1y2yt(modp).

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

detV=1j<kt(xkxj), 

which is zero mod p only when two of the xi’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 xk’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 (xk, yk). First, let

lk(x)=i=1iktxxixkxi(modp).

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

lk(xj)1 when k=j0 when kj.

This is because lk(xk) is a product of factors (xkxi)/(xkxi), all of which are 1. When kj, the product for lk(xj) contains the factor (xjxj)/(xkxj), which is 0.

The Lagrange interpolation polynomial

p(x)=k=1tyklk(x)

satisfies the requirement p(xj)=yj for 1jt. For example,

p(x1)=y1l1(x1)+y2l2(x2)+y11+y20+y1(modp).

We know from the previous approach with the Vandermonde matrix that the polynomial s(x) is the only one of degree t1 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

Mk=1tykj=1jktxjxkxj(modp).

Example

Let’s construct a (3, 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 s1 and s2 mod p and form the polynomial

s(x)=M+s1x+s2x2.

For example, let’s work with

s(x)=190503180520+482943028839x+1206749628665x2.

We now give the eight people pairs (x, s(x)). There is no need to choose the values of x randomly, so we simply use x=1, 2, , 8. Therefore, we distribute the following pairs, one to each person:

(1, 645627947891)(2, 1045116192326)(3, 154400023692)(4, 442615222255)(5, 675193897882)(6, 852136050573)(7, 973441680328)(8, 1039110787147).

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:

20705602144728/51986192751427x+(1095476582793/5)x2.

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

740740734080×51(modp), 

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

190503180520+482943028839x+1206749628665x2.

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:

1241391749Ms1s21045116192326154400023692973441680328(mod1234567890133).

This yields

(M, s1, s2)(190503180520, 482943028839, 1206749628665), 

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 ax2+bx+c passing through the points (0, 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, y7) yields a unique secret c, and any secret c yields a polynomial ax2+bx+c, which corresponds to y7=49a+7b+c. Therefore, every value of y7 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 t1, there is no way that t1 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 x0 be the secret. Choose y0, z0 randomly mod p. We therefore have a point Q=(x0, y0, z0) 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, b randomly mod p and then set cz0ax0by0(modp). The plane is then

z=ax+by+c.

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 x0 (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 x0, y0, z0, 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

aix+biyzci(modp), 1i3, 

which yield the matrix equation

a1b11a2b21a3b31x0y0z0c1c2c3.

As long as the determinant of this matrix is nonzero mod p, the matrix can be inverted mod p and the secret x0 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:

A:z=4x+19y+68B:z=52x+27y+10C:z=36x+65y+18D:z=57x+12y+16E:z=34x+19y+49.

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

41915227136651x0y0z0681018(mod73).

The solution is (x0, y0, z0)=(42, 29, 57), so the secret is x0=42. Similarly, any three of A, B, C, D, E can cooperate to recover x0.

By using (t1)-dimensional hyperplanes in t-dimensional space, we can use the same method to create a (t, 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, b, 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, y) versus (a, b, c, ).

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 scA+cB(modp). Now make cA into a secret shared among the employees of A as the constant term of a polynomial of degree 3. Similarly, let cB be the constant term of a polynomial of degree 2 and use this to distribute shares of cB among the employees of B. If four employees of A and three employees of B get together, then those from A determine cA and those from B determine cB. Then they add cA and cB to get s.

Note that A does not obtain any information about the secret s by itself since cA+xs(modp) has a unique solution x for every s, so every possible value of s corresponds to a possible value of cB. Therefore, knowing cA does not help A to find the secret; A also needs to know cB.