![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
THEOREM 11.1 Let C be any monotone boolean circuit. Then the monotone circuit construction yields a perfect secret sharing scheme realizing the access structure Γ(C). PROOF We proceed by induction on the number of gates in the circuit C. If C contains only one gate, then the result is fairly trivial: If C consists of one or gate, then every participant will be given the key. This scheme realizes the access structure consisting of all non-empty subsets of participants. If C consists of a single and gate with t inputs, then the scheme is the (t, t)-threshold scheme presented in Figure 11.2. Now, as an induction assumption, suppose that there is an integer j > 1 such that, for all circuits C with fewer than j gates, the construction produces a scheme that realizes Γ(C). Let C be a circuit on j gates. Consider the last gate, G, in the circuit; again, G could be either an or gate or an and gate. Lets first consider the case where G is an or gate. Denote the input wires to G by Wi, 1 ≤ i ≤ t. These t input wires are the outputs of t sub-circuits of C, which we denote Ci, 1 ≤ i ≤ t. Corresponding to each Ci, we have a (sub-)scheme that realizes the access structure ΓCi, by induction. Now, it is easy to see that Since every Wi is assigned the key K, it follows that the scheme realizes Γ(C), as desired. The analysis is similar if G is an and gate. In this situation, we have Since the key K is shared among the t wires Wi using a (t, t)-threshold scheme, it follows again that the scheme realizes Γ(C). This completes the proof. Of course, when an authorized subset, B, wants to compute the key, the participants in B need to know the circuit used by D to distribute shares, and which shares correspond to which wires of the circuit. All this information will be public knowledge. Only the actual values of the shares are secret. The algorithm for reconstructing the key involves combining shares according to the circuit, with the stipulation that an and gate corresponds to summing the values on the input wires modulo m (provided these values are all known), and an or gate involves choosing the value on any input wire (with the understanding that all these values will be identical). 11.4 Formal DefinitionsIn this section, we will give formal mathematical definitions of a (perfect) secret sharing scheme. We represent a secret sharing scheme by a set of distribution rules. A distribution rule is a function A distribution rule represents a possible distribution of shares to the participants, where f(Pi) is the share given to Pi, 1 ≤ i ≤ w. Now, for each Next, define
This is a completely general model in which we can study secret sharing schemes. Any of our existing schemes can be described in this setting by determining the possible distribution rules which the scheme will use. The fact that this model is mathematically precise makes it easier to give definitions and to present proofs. It is useful to develop conditions which ensure that a set of distribution rules for a scheme realizes a specified access structure. This will involve looking at certain probability distributions, as we did previously when studying the concept of perfect secrecy. To begin with, we suppose that there is a probability distribution Given these probability distributions, it is straightforward to compute the probability distribution on the list of shares given to any subset of participants, B (authorized or unauthorized). This is done as follows. Suppose where the function f|B denotes the restriction of the distribution rule f to B. That is, for all Pi ∈ B. Thus, The probability distribution on Also for all Here now is a formal definition of a perfect secret sharing scheme.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |