THEOREM 11.5

Suppose G = (V, E) is a complete multipartite graph. Then there is an ideal scheme realizing the access structure cl (E) on participant set V.

PROOF  Let be the parts of G. Let be distinct elements of , where . Let d = 2. For every participant v ∈ V_i, define φ(v) = (x_i, 1).

It is straightforward to verify Property (11.3). By Theorem 11.4, we have an ideal scheme.

To illustrate the application of these constructions, we will consider the possible access structures for up to four participants. Note that it suffices to consider only the access structures in which the basis cannot be partitioned into two non-empty subsets on disjoint participant sets. (For example, Γ₀ = {{P₁, P₂}, {P₃, P₄}} can be partitioned as {{P₁, P₂}} ∪ {{P₃, P₄}} so we do not consider it.) We list the non-isomorphic access structures of this type on two, three, and four participants in Table 11.1 (the quantities ρ* are defined in Section 11.7).

Of these 18 access structures, we can already obtain ideal schemes for ten of them using the constructions we have at our disposal now. These ten access structures are either threshold access structures or have a basis which is a complete multipartite graph, so Theorem 11.5 can be applied. One such access structure is # 9, whose basis is the complete multipartite graph K_1,1,2. We illustrate in the following example.

Example 11.7

For access structure # 9, take d = 2, p ≥ 3, and define φ as follows: