Cryptography: Theory and Practice:Secret Sharing Schemes

cryptography: theory and practice Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210   Pub Date: 03/17/95
  

Previous Table of Contents Next


Chapter 11
Secret Sharing Schemes

11.1 Introduction: The Shamir Threshold Scheme

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 pw + 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.

Let’s 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 ≤ jt, 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 ≤ jt, 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 ≤ jt, 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 xi’s 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



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net