![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
THEOREM 11.2 Let C be any monotone boolean circuit. Then there is a perfect secret sharing scheme realizing the access structure Γ(C) having information rate where ri denotes the number of input wires to C carrying the input xi. With respect to threshold access structures, we observe that the Shamir scheme will have information rate 1, which we show below is the optimal value. In contrast, an implementation of a (t, w)-threshold scheme using a disjunctive normal form boolean circuit will have information rate Obviously, a high information rate is desirable. The first general result we prove is that ρ ≤ 1 in any scheme. THEOREM 11.3 In any perfect secret sharing scheme realizing an access structure Γ, ρ ≤ 1. PROOF Suppose we have a a perfect secret sharing scheme that realizes the access structure Γ. Let B ∈ Γ0 and choose any participant Pj ∈ B. Define B′ = B\{Pj}. Let Since ρ = 1 is the optimal situation, we refer to such a scheme an ideal scheme. The Shamir schemes are ideal schemes. In the next section, we present a construction for ideal schemes that generalizes the Shamir schemes. 11.6 The Brickell Vector Space ConstructionIn this section, we present a construction for certain ideal schemes known as the Brickell vector space construction. Suppose Γ is an access structure, and let which satisfies the property
In other words, the vector (1, 0, . . . , 0) can be expressed as a linear combination of the vectors in the set {φ(Pi) : Pi ∈ B} if and only if B is an authorized subset. Now, suppose there is a function φ that satisfies Property (11.3). (In general, finding such a function is often a matter of trial and error, though we will see some explicit constructions of suitable functions φ for certain access structures a bit later.) We are going to construct an ideal secret sharing scheme with for every Note that each We have the following result. THEOREM 11.4 Suppose φ satisfies Property (11.3). Then the sets of distribution rules PROOF First, we will show that if B is an authorized subset, then the participants in B can compute K. Since we can write where each where By the linearity of the inner product operation, Thus, it is a simple matter for the participants in B to compute What happens if B is not an authorized subset? Denote by e the dimension of the subspace 〈φ(Pi) : Pi ∈ B〉 (note that e ≤ |B|). Choose any This is a system of linear equations in the d unknowns a1, . . . , ad. The coefficient matrix has rank e + 1, since Provided the system of equations is consistent, the solution space has dimension d - e - 1 (independent of the value of K). It will then follow that there are precisely pd-e-1 distribution rules in each Why is the system consistent? The first |B| equations are consistent, since the vector (as mentioned above) the last equation is consistent with the first |B| equations. This completes the proof. It is interesting to observe that the Shamir (t, w)-threshold scheme is a special case of the vector space construction. To see this, define d = t and let for 1 ≤ i ≤ w, where xi is the x-coordinate given to Pi. The resulting scheme is equivalent to the Shamir scheme; we leave the details to the reader to check. Here is another general result that is easy to prove. It concerns access structures that have as a basis a collection of pairs of participants that forms a complete multipartite graph. A graph G = (V, E) with vertex set V and edge set E is defined to be a complete multipartite graph if the vertex set V can be partitioned into subsets
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |