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.2

Let C be any monotone boolean circuit. Then there is a perfect secret sharing scheme realizing the access structure Γ(C) having information rate

where r_i denotes the number of input wires to C carrying the input x_i.

With respect to threshold access structures, we observe that the Shamir scheme will have information rate 1, which we show below is the optimal value. In contrast, an implementation of a (t, w)-threshold scheme using a disjunctive normal form boolean circuit will have information rate , which is much lower (and therefore inferior) if 1 < t < w.

Obviously, a high information rate is desirable. The first general result we prove is that ρ ≤ 1 in any scheme.

THEOREM 11.3

In any perfect secret sharing scheme realizing an access structure Γ, ρ ≤ 1.

PROOF Suppose we have a a perfect secret sharing scheme that realizes the access structure Γ. Let B ∈ Γ₀ and choose any participant P_j ∈ B. Define B′ = B\{P_j}. Let . Now, B′ ∉ Γ, so the distribution of shares g|_B′ provides no information about the key. Hence, for each , there is a distribution rule such that g^K|_B′ = g|_B′. Since B ∈ Γ, it must be the case that g^K (P_j) ≠ g^K′ (P_j) if K ≠ K′. Hence, and thus ρ ≤ 1.

Since ρ = 1 is the optimal situation, we refer to such a scheme an ideal scheme. The Shamir schemes are ideal schemes. In the next section, we present a construction for ideal schemes that generalizes the Shamir schemes.

11.6 The Brickell Vector Space Construction

In this section, we present a construction for certain ideal schemes known as the Brickell vector space construction.

Suppose Γ is an access structure, and let denote the vector space of all d-tuples over , where p is prime and d ≥ 2. Suppose there exists a function

which satisfies the property

Figure 11.6 The Brickell scheme

In other words, the vector (1, 0, . . . , 0) can be expressed as a linear combination of the vectors in the set {φ(P_i) : P_i ∈ B} if and only if B is an authorized subset.

Now, suppose there is a function φ that satisfies Property (11.3). (In general, finding such a function is often a matter of trial and error, though we will see some explicit constructions of suitable functions φ for certain access structures a bit later.) We are going to construct an ideal secret sharing scheme with . The distribution rules of the scheme are as follows: for every vector , define a distribution rule , where

for every , and the operation “·” is the inner product modulo p.

Note that each contains p^d-1 distribution rules. We will suppose that each probability distribution is equiprobable: for every . The Brickell scheme is presented in Figure 11.6

We have the following result.

THEOREM 11.4

Suppose φ satisfies Property (11.3). Then the sets of distribution rules , comprise an ideal scheme that realizes Γ.

PROOF First, we will show that if B is an authorized subset, then the participants in B can compute K. Since

we can write

where each . Denote by s_i the share given to P_i. Then

where is an unknown vector chosen by D and

By the linearity of the inner product operation,

Thus, it is a simple matter for the participants in B to compute

What happens if B is not an authorized subset? Denote by e the dimension of the subspace 〈φ(P_i) : P_i ∈ B〉 (note that e ≤ |B|). Choose any , and consider the system of equations:

This is a system of linear equations in the d unknowns a₁, . . . , a_d. The coefficient matrix has rank e + 1, since

Provided the system of equations is consistent, the solution space has dimension d - e - 1 (independent of the value of K). It will then follow that there are precisely p^d-e-1 distribution rules in each that are consistent with any possible distribution of shares to B. By a similar computation as was performed in Example 11.5, we see that for every , where f_B(P_i) = s_i for all P_i ∈ B.

Why is the system consistent? The first |B| equations are consistent, since the vector chosen by D is a solution. Since

(as mentioned above) the last equation is consistent with the first |B| equations. This completes the proof.

It is interesting to observe that the Shamir (t, w)-threshold scheme is a special case of the vector space construction. To see this, define d = t and let

for 1 ≤ i ≤ w, where x_i is the x-coordinate given to P_i. The resulting scheme is equivalent to the Shamir scheme; we leave the details to the reader to check.

Here is another general result that is easy to prove. It concerns access structures that have as a basis a collection of pairs of participants that forms a complete multipartite graph. A graph G = (V, E) with vertex set V and edge set E is defined to be a complete multipartite graph if the vertex set V can be partitioned into subsets such that {x, y} ∈ E if and only if x ∈ V_i, y ∈ V_j, where i ≠ j. The sets V_i are called parts. The complete multipartite graph is denoted by if . A complete multipartite graph K_{1, . . . , 1} (with parts) is in fact a complete graph and is denoted .

Table of Contents