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 a₁, a₂, K - a₁ - a₂, respectively, where all arithmetic is done in . In a similar way, the three input wires corresponding to are assigned values b₁, b₂, K - b₁ - b₂. Finally, the two input wires corresponding to are assigned values c_i, K - c₁. Note that a₁, a₂, b₁, b₂ and c₁ are all independent random values in . If we look at the shares that the four participants receive, we have the following:

1.  P₁ receives a ₁, b₁.

2.  P₂ receives a₂, c₁.

3.  P₃ receives b₂, K - c₁.

4.  P₄ receives K - a₁ - a₂, K - b₁ - b₂.

Figure 11.3  The monotone circuit construction

Thus, every participant receives two elements of as his or her share.

Let’s prove that the scheme is perfect. First, we verify that each basis subset can compute K. The authorized subset {P₁, P₂, P₄} can compute

The subset {P₁, P₃, P₄} can compute

Finally, the subset {P₂, P₃} 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 B₁ and B₂ are both unauthorized subsets, , and B₂ cannot compute K, then neither can B₁ compute K. Define a subset to be a maximal unauthorized subset if B₁ ∈ Γ 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 {P₁, P₂} possesses only the random values a₁, b₁, a₂, c₁. As another example, the subset {P₃, P₄} possesses the shares b₂, K - c₁, K - a₁ - a₂, K - b₁ - b₂. Since the values of c₁, a₁, a₂, and b₁ 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:

1.  P₁ receives a₁, a₂.

2.  P₂ receives a₁, a₃, a₄.

3.  P₃ receives a₂, a₃, K - a₁ - a₂ - a₃ - a₄.

4.  P₄ receives a₄, K - a₁ - a₂ - a₃ - a₄.

We leave the details for the reader to check.

We now prove that the monotone circuit construction always produces a perfect secret sharing scheme.