![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
What happens if a group of t - 1 participants attempt to compute K? Proceeding as above, they will obtain a system of t - 1 equations in t unknowns. Suppose they hypothesize a value y0 for the key. Since the key is a0 = a(0), this will yield a tth equation, and the coefficient matrix of the resulting system of t equations in t unknowns will again be a Vandermonde matrix. As before, there will be a unique solution. Hence, for every hypothesized value y0 of the key, there is a unique polynomial ay0(x) such that 1 ≤ j ≤ t - 1, and such that Hence, no value of the key can be ruled out, and thus a group of t - 1 participants can obtain no information about the key. We have analyzed the Shamir scheme from the point of view of solving systems of linear equations over It is easy to verify the correctness of this formula by substituting A group B of t participants can compute a(x) by using the interpolation formula. But a simplification is possible, since the participants in B do not need to know the whole polynomial a(x). It is sufficient for them to compute the constant term K = a(0). Hence, they can compute the following expression, which is obtained by substituting x = 0 into the Lagrange interpolation formula: Suppose we define 1 ≤ j ≤ t. (Note that these values bj can be precomputed, if desired, and their values are not secret.) Then we have Hence, the key is a linear combination of the t shares. To illustrate this approach, lets recompute the key from Example 11.1. Example 11.1 (Cont.) The participants {P 1, P3, P5} can compute b1, b2, and b3 according to the formula given above. For example, they would obtain Similarly, b2 = 3 and b3 = 11. Then, given shares 8, 10, and 11 (respectively), they would obtain as before. The last topic of this section is a simplified construction for threshold schemes in the special case w = t. This construction will work for any key set
Observe that the t participants can compute K by the formula Can t - 1 participants compute K? Clearly, the first t - 11 participants cannot do so, since they receive t - 1 independent random numbers as their shares. Consider the t - 1 participants in the set and By summing their shares, they can compute K - yi. However, they do not know the random value yi, and hence they have no information as to the value of K. Consequently, we have a (t, t)-threshold scheme. 11.2 Access Structures and General Secret SharingIn the previous section, we desired that any t of the w participants should be able to determine the key. A more general situation is to specify exactly which subsets of participants should be able to determine the key and which should not. Let Γ be a set of subsets of Let DEFINITION 11.2 A perfect secret sharing scheme realizing the access structure Γ is a method of sharing a key K among a set of w participants (denoted by
Observe that a (t, w)-threshold scheme realizes the access structure Such an access structure is called a threshold access structure. We showed in the previous section that the Shamir scheme is a perfect scheme realizing the threshold access structure. We study the unconditional security of secret sharing schemes. That is, we do not place any limit on the amount of computation that can be performed by an unauthorized subset of participants. Suppose that B ∈ Γ and In the remainder of this chapter, we will assume that all access structures are monotone.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |