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


DEFINITION 11.3  Suppose Γ is an access structure and is a set of distribution rules. The is a perfect secret sharing scheme realizing the access structure Γ provided that the following two properties are satisfied:

1.  For any authorized subset of participants , there do not exist two distribution rules and with K ≠ K’, such that f|B = f’|B. (That is, any distribution of shares to the participants in an authorized subset B determines the value of the key.)
2.  For any unauthorized subset of participants and for any distribution of shares for every . (That is, the conditional probability distribution on , given a distribution of shares fB to an unauthorized subset B, is the same as the a priori probability distribution on . In other words, the distribution of shares to B provides no information as to the value of the key.)


Figure 11.5  Distribution rules for a secret sharing scheme

Observe that the second property in Definition 11.3 is very similar to the concept of perfect secrecy; this similarity is why the resulting secret sharing scheme is termed “perfect.”

Note that the probability can be computed from probability distributions exhibited above using Bayes’ theorem:

Let us now illustrate these definitions by looking at a small example.

Example 11.5

We will present the distribution rules for the scheme constructed in Example 11.4 when it is implemented in . Each of and contains 16 equiprobable distribution rules. For conciseness, we replace a binary k-tuple by an integer between 0 and 2k - 1. If this is done, then and are as depicted in Figure 11.5, where each row represents a distribution rule.

This yields a perfect scheme for any probability distribution on the keys. We will not perform all the verifications here, but we will look at a couple of typcial cases to illustrate the use of the two properties in Definition 11.3.

The subset {P2, P3} is an authorized subset. Thus the shares that P2 and P3 receive should (together) determine a unique key. It can easily be checked that any distribution of shares to these two participants occurs in a distribution rule in at most one of the sets and . For example, if P2 has the share 3 and P3 has the share 6, then the distribution rule must be the eighth rule in and thus the key is 0.

On the other hand, B = {P1, P2} is an unauthorized subset. It is not too hard to see that any distribution of shares to these two participants occurs in exactly one distribution rule in and in exactly one distribution rule in . That is,

for any and for K = 0, 1. Next, we compute

Now, we use Bayes’ theorem to compute :

so the second property is satisfied for this subset B.

Similar computations can be performed for other authorized and unauthorized sets, and in each case the appropriate property is satisfied. Hence we have a perfect secret sharing scheme.

11.5 Information Rate

The results of Section 11.3 prove that any monotone access structure can be realized by a perfect secret sharing scheme. We now want to consider the efficiency of the resulting schemes. In the case of a (t, w)-threshold scheme, we can construct a circuit corresponding to the disjunctive normal form boolean formula which will have gates. Each participant will receive elements of as his or her share. This seems very inefficient, since a Shamir (t, w)-threshold scheme enables a key to be shared by giving each participant only one “piece” of information.

In general, we measure the efficiency of a secret sharing scheme by the information rate, which we define now.

DEFINITION 11.4  Suppose we have a perfect secret sharing scheme realizing an access structure Γ. The information rate for Pi is the ratio

(Note that denotes the set of possible shares that Pi might receive; of course The information rate of the scheme is denoted by ρ and is defined as

The motivation for this definition is as follows. Since the key K comes from a finite set , we can think of K as being represented by a bit-string of length , by using a binary encoding, for example. In a similar way, a share given to Pi can be represented by a bit-string of length . Intuitively, Pi receives bits of information (in his or her share), but the information content of the key is bits. Thus ρi is the ratio of the number of bits in a share to the number of bits in the key.

Example 11.6

Let’s look at the two schemes from Section 11.2. The scheme produced in Example 11.3 has

However, in Example 11.4, we get a scheme with

Hence, the first implementation is preferable.

In general, if we construct a scheme from a circuit C using the monotone circuit construction, then the information rate can be computed as indicated in the following theorem.


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