![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
DEFINITION 11.3 Suppose Γ is an access structure and
Observe that the second property in Definition 11.3 is very similar to the concept of perfect secrecy; this similarity is why the resulting secret sharing scheme is termed perfect. Note that the probability Let us now illustrate these definitions by looking at a small example. Example 11.5 We will present the distribution rules for the scheme constructed in Example 11.4 when it is implemented in This yields a perfect scheme for any probability distribution The subset {P2, P3} is an authorized subset. Thus the shares that P2 and P3 receive should (together) determine a unique key. It can easily be checked that any distribution of shares to these two participants occurs in a distribution rule in at most one of the sets On the other hand, B = {P1, P2} is an unauthorized subset. It is not too hard to see that any distribution of shares to these two participants occurs in exactly one distribution rule in for any Now, we use Bayes theorem to compute so the second property is satisfied for this subset B. Similar computations can be performed for other authorized and unauthorized sets, and in each case the appropriate property is satisfied. Hence we have a perfect secret sharing scheme. 11.5 Information RateThe results of Section 11.3 prove that any monotone access structure can be realized by a perfect secret sharing scheme. We now want to consider the efficiency of the resulting schemes. In the case of a (t, w)-threshold scheme, we can construct a circuit corresponding to the disjunctive normal form boolean formula which will have In general, we measure the efficiency of a secret sharing scheme by the information rate, which we define now. DEFINITION 11.4 Suppose we have a perfect secret sharing scheme realizing an access structure Γ. The information rate for Pi is the ratio (Note that The motivation for this definition is as follows. Since the key K comes from a finite set Example 11.6 Lets look at the two schemes from Section 11.2. The scheme produced in Example 11.3 has However, in Example 11.4, we get a scheme with Hence, the first implementation is preferable. In general, if we construct a scheme from a circuit C using the monotone circuit construction, then the information rate can be computed as indicated in the following theorem.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |