![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
Suppose Γ is an access structure having basis Γ0, and Then there exists a perfect secret sharing scheme realizaing Γ, having information rate PROOF For The information rate can be computed in a manner similar to that of Theorem 11.12. Let's look at a couple of examples. Example 11.10 Consider access structure # 5. The basis is a graph that is not a complete multi-partite graph. Therefore we know from Theorem 11.11 that ρ* ≤ 2/3. Let p be prime, and consider the following two ideal where and where Each decomposition consists of a K2 and a K1,2, so they are indeed ideal One implementation of the scheme, using Theorem 11.5, is as follows. D will choose four random elements (independently) from
(All arithmetic is performed in Example 11.11 Consider access structure # 8. Again, ρ* ≤ 2/3 by Theorem 11.11, and two suitable ideal compositions will yield an (optimal) scheme with ρ = 2/3. Take where and where
One implementation, using Theorem 11.5, is as follows. D will choose four random elements (independently) from
(All arithmetic is performed in To this point, we have explained all the information in Table 11.1 except for the values of ρ* for access structures # 12 and # 13. These values arise from a more general version of the decomposition construction which we do not describe here; see the notes below. 11.9 Notes and ReferencesThreshold schemes were invented independently by Blakley [BL79] and Shamir [SH79]. Secret sharing for general access structures was first studied in Ito, Saito, and Nishizeki [ISN87]; we based Section 11.2 on the approach of Benaloh and Leichter [BL90]. The vector space construction is due to Brickell [BR89A]. The entropy bound of Section 11.7 is proved in Capocelli et al. [CDGV93], and some of the other material from this section is found in Blundo et al. [BDSV93]. In this chapter, we have emphasized a linear-algebraic and combinatorial approach to secret sharing. Some interesting connections with matroid theory can be found in Brickell and Davenport [BD91]. Secret sharing schemes can also be constructed using geometric techniques. Simmons has done considerable research in this direction; we refer to [SI92A] for an overview of geometric techniques in secret sharing. Further discussion of these topics, as well as constructions for schemes having information rate 2/3 for access structures # 12 and # 13, can be found in the expository paper by Stinson [ST92A].
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |