Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
Example 11.3
We illustrate the construction in Figure 11.4. Suppose K is the key. The value K is given to each of the three input wires of the final or gate. Next, we consider the and gate corresponding to the clause . The three input wires are assigned values a1, a2, K - a1 - a2, respectively, where all arithmetic is done in . In a similar way, the three input wires corresponding to are assigned values b1, b2, K - b1 - b2. Finally, the two input wires corresponding to are assigned values ci, K - c1. Note that a1, a2, b1, b2 and c1 are all independent random values in . If we look at the shares that the four participants receive, we have the following:
Figure 11.3 The monotone circuit construction
Thus, every participant receives two elements of as his or her share.
Lets prove that the scheme is perfect. First, we verify that each basis subset can compute K. The authorized subset {P1, P2, P4} can compute
The subset {P1, P3, P4} can compute
Finally, the subset {P2, P3} can compute
Figure 11.4 A monotone circuit
Thus any authorized subset can compute K, so we turn our attention to the unauthorized subsets. Note that we do not need to look at all the unauthorized subsets. For, if B1 and B2 are both unauthorized subsets, , and B2 cannot compute K, then neither can B1 compute K. Define a subset to be a maximal unauthorized subset if B1 ∈ Γ for all . It follows that it suffices to verify that none of the maximal unauthorized subsets can determine any information about K. Here, the maximal unauthorized subsets are
In each case, it is easy to see that K cannot be computed, either because some necessary piece of random information is missing, or because all the shares possessed by the subset are random. For example, the subset {P1, P2} possesses only the random values a1, b1, a2, c1. As another example, the subset {P3, P4} possesses the shares b2, K - c1, K - a1 - a2, K - b1 - b2. Since the values of c1, a1, a2, and b1 are unknown random values, K cannot be computed. In each possible case, an unauthorized subset has no information about the value of K.
We can obtain a different scheme realizing the same access structure by using a different circuit. We illustrate by returning again to the access structure of Example 11.2.
Example 11.4
Suppose we convert the formula (11.1) to the so-called conjunctive normal form:
(The reader can verify that this formula is equivalent to the formula (11.1).) If we implement the scheme using the circuit corresponding to formula (11.2), then we obtain the following:
We leave the details for the reader to check.
We now prove that the monotone circuit construction always produces a perfect secret sharing scheme.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC