Cryptography: Theory and Practice:Secret Sharing Schemes | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

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. Let’s first consider the case where G is an “or” gate. Denote the input wires to G by W_i, 1 ≤ i ≤ t. These t input wires are the outputs of t sub-circuits of C, which we denote C_i, 1 ≤ i ≤ t. Corresponding to each C_i, we have a (sub-)scheme that realizes the access structure ΓC_i, by induction. Now, it is easy to see that

Since every W_i 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 W_i 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 Definitions

In 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(P_i) is the share given to P_i, 1 ≤ i ≤ w.

Now, for each , let be a set of distribution rules. will be distribution rules corresponding to the key having the value K. The sets of distribution rule are public knowledge.

Next, define

is the complete set of distribution rules of the scheme. If is the value of the key that D wishes to share, then D will choose a distribution rule , and use it to distribute shares.

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 on . Further, for every , D will choose a distribution rule in according to 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 . Define