Cryptography: Theory and Practice:Secret Sharing Schemes | Modern Cryptography: Theory and Practice

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

Table of Contents

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:

**Table 11.1** Access structures for at most four participants
	w	subsets in Γ₀	ρ*	comments
1.	2	P₁P₂	1	(2, 2)-threshold
2.	3	P₁P₂, P₂P₃	1	Γ₀ ≅ K_1,2
3.	3	P₁P₂, P₂P₃, P₁P₃	1	(2, 3)-threshold
4.	3	P₁P₂P₃	1	(3, 3)-threshold
5.	4	P₁P₂, P₂P₃, P₃P₄	2/3
6.	4	P₁P₂, P₁P₃, P₁P₄	1	Γ₀ ≅ K_1,3
7.	4	P₁P₂, P₁P₄, P₂P₃, P₃P₄	1	Γ₀ ≅ K_2,2
8.	4	P₁P₂, P₂P₃, P₂P₄, P₃P₄	2/3
9.	4	P₁P₂, P₁P₃, P₁P₄, P₂P₃, P₂P₄	1	Γ₀ ≅ K_1,1,2
10.	4	P₁P₂, P₁P₃, P₁P₄, P₂P₃, P₂P₄, P₃P₄	1	(2, 4)-threshold
11.	4	P₁P₂P₃, P₁P₄	1
12.	4	P₁P ₃P₄, P₁P₂, P₂P₃	2/3
13.	4	P₁P₃P₄,P₁P₂, P₂P₃, P₂P₄	2/3
14.	4	P₁P₂P₃, P₁P₂P₄	1
15.	4	P₁P₂P₃, P₁P₂P₄, P₃P₄	1
16.	4	P₁P₂P₃, P₁P₂P₄, P₁P₃P₄	1
17.	4	P₁P₂P₃, P₁P₂P₄, P₁P₃P₄, P₂P₃P₄	1	(3, 4)-threshold
18.	4	P₁P₂P₃P₄	1	(4, 4)-threshold

Table of Contents