Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
In a bank, there is a vault which must be opened every day. The bank employs three senior tellers, but they do not trust the combination to any individual teller. Hence, we would like to design a system whereby any two of the three senior tellers can gain access to the vault, but no individual teller can do so. This problem can be solved by means of a secret sharing scheme, the topic of this chapter.
Here is an interesting real-world example of this situation: According to Time-Magazine1, control of nuclear weapons in Russia involves a similar two-out-of-three access mechanism. The three parties involved are the President, the Defense Minister and the Defense Ministry.
1 Time Magazine, May 4, 1992, p. 13
We first study a special type of secret sharing scheme called a threshold scheme. Here is an informal definition.
DEFINITION 11.1 Let t, w be positive integers, t ≤ w. A (t, w) -threshold scheme is a method of sharing a key K among a set of w participants (denoted by ), in such a way that any t participants can compute the value of K, but no group of t - 1 participants can do so.
Note that the examples described above are (2, 3)-threshold schemes.
The value of K is chosen by a special participant called the dealer. The dealer is denoted by D and we assume . When D wants to share the key K among the participants in , he gives each participant some partial information called a share. The shares should be distributed secretly, so no participant knows the share given to another participant.
At a later time, a subset of participants will pool their shares in an attempt to compute the key K. (Alternatively, they could give their shares to a trusted authority which will perform the computation for them.) If |B| ≥ t, then they should be able to compute the value of K as a function of the shares they collectively hold; if |B| < t, then they should not be able to compute K.
Figure 11.1 The Shamir (t, w)-threshold scheme in
We will use the following notation. Let
be the set of w participants. is the key set (i.e., the set of all possible keys); and is the share set (i.e., the set of all possible shares).
In this section, we present a method of constructing a (t, w)-threshold scheme, called the Shamir Threshold Scheme, which was invented in 1979. Let where p ≥ w + 1 is prime. Also, let . Hence, the key will be an element of , as will be each share given to a participant. The Shamir threshold scheme is presented in Figure 11.1. In this scheme, the dealer constructs a random polynomial a(x) of degree at most t - 1 in which the constant term is the key, K. Every participant Pi obtains a point (xi, yi) on this polynomial.
Lets look at how a subset B of t participants can reconstruct the key. This is basically accomplished by means of polynomial interpolation. We will describe a couple of methods of doing this.
Suppose that participants want to determine K. They know that
1 ≤ j ≤ t, where is the (secret) polynomial chosen by D. Since a(x) has degree at most t - 1, a(x) can be written as
where the coefficients a0, . . . , at-1 are unknown elements of , and a0 = K is the key. Since , 1 ≤ j ≤ t, B can obtain t linear equations in the t unknowns a0, . . . , at-1, where all arithmetic is done in . If the equations are linearly independent, there will be a unique solution, and a0 will be revealed as the key.
Here is a small example to illustrate.
Example 11.1
Suppose that p = 17, t = 3, and w = 5; and the public x-co-ordinates are xi = i, 1 ≤ i ≤ 5. Suppose that B = {P1, P3, P5} pool their shares, which are respectively 8, 10, and 11. Writing the polynomial a(x) as
and computing a(1), a(3) and a(5), the following three linear equations in are obtained:
This system does have a unique solution in . The key is therefore K = a0 = 13.
Clearly, it is important that the system of t linear equations has a unique solution, as in Example 11.1. We show now that this is always the case. In general, we have
1 ≤ j ≤ t, where
and
The system of linear equations (in ) is the following:
This can be written in matrix form as follows:
Now, the coefficient matrix A is a so-called Vandermonde matrix. There is a well-known formula for the determinant of a Vandermonde matrix, namely
Recall that the xis are all distinct, so no term in this product is equal to zero. The product is computed in , where p is prime, which is a field. Since the product non-zero terms in a field is always non-zero, we have that det A ≠ 0. Since the determinant of the coefficient matrix is non-zero, the system has a unique solution over the field . This establishes that any group of t participants will be able to recover the key in this threshold scheme.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC