Sebery J.Cryptography.An introduction to computer security.1989

9.1 Threshold Secret Sharing

331

9.1.3 Blakley Scheme

Blakley [41] used projective spaces to construct a (t; n) threshold scheme. The dealer chooses a projective space of dimension t over GF (q). Denote the space

(qt 1)

by P G(t; q). Next Don selects at random a point p 2 P G(t; q). There are (q 1) subspaces of dimension (t 1). A subspace of dimension (t 1) is called a

hyperplane. Shares are di erent hyperplanes P G(t 1; q) that contain the point p. The shares are distributed to all participants.

At the pooling time, the combiner takes the provided collection of hyperplanes and nds their intersection, the point p. The secret cannot be reconstructed when Clara has t 1 or fewer hyperplanes as the intersection is a subspace containing p.

A modi cation of the scheme based on aÆne spaces was suggested by Simmons in [475].

9.1.4 Modular Scheme

Asmuth and Bloom used congruence classes to de ne threshold schemes [9].

Assume that every participant Pi		2 P		is assigned a public modulus pi;
i = 1; : : : ; n. The moduli can be primes or mutually coprimes. The secret k
belongs to	Zp0 where the modulus p0	is public and mutually coprime to pi;
i = 1; : : : ; n. Let the moduli be such that p0 < p1 < : : : < pn. The dealer selects
at random an integer s such that 0 < s <				it=1 pi. The secret k		s (mod p0).
Next the dealer distributes shares			Q
si s	(mod pi)

to the participants Pi (i = 1; : : : ; n) via secure channels.

Assume that there are t or more participants who want to recreate the secret. The combiner takes their shares si1 ; : : : ; sit and solves the following system of congruences:

si1	s	(mod pi1 )
	.
	.	(9.3)
	.
sit	s	(mod pit)

According to the Chinese Remainder Theorem, the system (9.3) has the unique

Q
solution that is 0 < s < jt=1 pij . The secret is k		s (mod p0).

332 9 SECRET SHARING

Note that the condition 0 < s < Qti=1 pi is necessary for the combiner to be able to recompute the unique s and nd the correct secret k. Note also that s is always smaller than any product of t moduli as p1 < : : : < pn. Security of the scheme is discussed in [421].

Let us build a (2; 4) threshold scheme. First we select public moduli: p0 = 17, p1 = 19, p2 = 23, p3 = 29, and p4 = 31. The dealer selects a secret number s

randomly from	Z19 23 = Z437. Let it be s = 241. Then the secret k = 3 241
(mod 17). The shares are s1 = 13 241		(mod 19), s2 = 11 241 (mod 23),
s3 = 9 241	(mod 29), and s4 =	24 241 (mod 31). The shares are
communicated securely to all four participants. Assume that the combiner has

received two shares from P2 and P4. Clara can easily solve the following system of congruences:

11 s (mod 29)

24 s (mod 31)

According to the Chinese Remainder Theorem, there is the solution s = 241. Clearly, the secret k = 3 241 (mod 17).

The modular scheme can be modi ed to work with polynomials instead of integers.

9.2 General Secret Sharing

A (t; n) threshold scheme allows any group of t or more participants to access the secret. The access structure is the collection of all subsets of participants who are able to access the secret. In other words, the access structure of (t; n) threshold schemes is

= fA 2 2P : jAj tg

where 2P is the class of all subsets of P (or 2P consists of all possible groups which can be created from P). The access structure, in this case, consists of all groups whose cardinality is at least t. These groups are also called authorized subsets. On the other hand, an unauthorized subset is a group that does not belong to or the cardinality of the group is smaller than t.

In general, however, secret sharing may have a far more complicated access structure than those from (t; n) threshold scheme. Let the set of all participants be P = fP1; : : : ; Png. We split the class 2P of all subsets of P into two disjoint

its supersets B

9.2 General Secret Sharing

333

subclasses: the class of all authorized subsets of P, and the class 2P n of all unauthorized subsets of P. An authorized subset of participants is the one that is able to recover the secret k 2 K while any unauthorized subset is not. The access structure is the class of all authorized subsets of P.

Benaloh and Leichter observed in [24] that any reasonable access structure should be monotone, which means that an authorized group remains authorized if additional users join.

De nition 26. An access structure is monotone if for any subset A 2 all are contained in , that is

if A 2 and A B; then B 2 :

Take a closer look at . Among the elements (subsets) of we can identify minimal subsets. A subset A 2 is minimal if for all B A, the subset B does not belong to the access structure . The collection of all minimal subset of is called the access structure basis 0 and

0 = fA 2 j 8B AB 2= g:

The basis 0 of a (t; n) threshold scheme is

0 = fA 2 2P : jAj = tg:

Because of the monotone property, the access structure basis 0 can always be expanded to by including all supersets generated from the sets of 0 , i.e.

= cl( 0) = fA : A B; B 2 0g

where cl( 0) is the closure of 0.

A general secret sharing over the access structure is de ned as follows.

De nition 27. A secret sharing scheme over a (monotone) access structure with n participants is a collection of two algorithms. The rst algorithm, called the dealer

D : K ! S1 S2 Sn;

assigns shares to the participants for a secret k 2 K. The share si 2 Si is communicated via a secure channel to the participant Pi.

The second algorithm (the combiner)

C : Si1 Si2 Sij ! K

334 9 SECRET SHARING

takes an arbitrary collection of shares and attempts to compute the secret. The combiner recovers the secret only if the set of cooperating participants fPi1 ; Pi2 ; : : : ; Pij g 2 . It fails if the set of active participants is not in .

9.2.1 Cumulative Array Construction

Ito, Saito, and Nishizeki showed how a monotone access structure can be realized as a perfect secret sharing scheme [256]. We are going to illustrate their method by using the so-called cumulative array.

First note that for every access structure , there is a unique collection of maximal unauthorized subsets. More formally, for a given , we de ne

M = fB1; : : : ; Bmg

such that each Bi 2= , but

Bi [ Pj 2

for any Pj 2= Bi. The collection M contains all possible maximal unauthorized subsets.

Consider an example for the following access structure

= cl(ffP1; P2g; fP3; P4gg)

where P = fP1; P2; P3; P4g. The collection M = fB1; B2; B3; B4g = ffP1; P3g, fP1; P4g, fP2; P3g, fP2; P4gg. Consider the subset fP2; P3g. Any extra element either P1 or P4 added to it, converts it to an authorized subset.

Every access structure can be associated with a Boolean function (P1;

: : : ; Pn) that becomes 1 for any subset A 2 and 0, otherwise. The subset A can be equivalently represented by the assignment (P1 = p1; : : : ; Pn = pn) for which Pi 2 A i pi = 1. More formally, the Boolean function (P1; : : : ; Pn) is de ned as follows:

1 if		Pi		pi = 1; i = 1; : : : ; n
(P1 = p1; : : : ; Pn = pn) = (0	f		j	otherwise	g 2

For instance, if = cl(ffP1; P2g; fP3; P4gg) the corresponding Boolean function is (P1; P2; P3; P4) = P1P2 + P3P4.

From now on, we assume that the function (P1; : : : ; Pn) is always in the canonical sum-of-product form (or disjunctive normal form).

Given a Boolean function (P1; : : : ; Pn). De ne the dual Boolean function(P1; P2; : : : ; Pn) that is generated from (P1; P2; : : : ; Pn) by swapping OR

9.2 General Secret Sharing

335

with AND operators. The function is also associated with the corresponding access structure . We call it the dual access structure.

For instance, for (P1; P2; P3; P4) = P1P2 + P3P4, its dual function

(P1; P2; P3; P4) = (P1 + P2)(P3 + P4) = P1P3 + P1P4 + P2P3 + P2P4:

The dual access structure is = cl(ffP1; P3g;fP1; P4g; fP2; P3g; fP2; P4gg). Now we follow the observation made in [477], which links duality with the

collection M of maximal unauthorized subsets.

Theorem 39. Given access structure with the collection of maximal unau-

thorized subsets M = fB1; : : : ; Bmg and its dual = fA1; : : : ; Amg where Ai P. Then

Bi = P n Ai:

for i = 1; : : : ; m.

Now we are ready to de ne the notion of cumulative array.

De nition 28. Given = cl( 0) for n participants with the corresponding collection M= fB1, : : :, Bmg of maximal unauthorized subsets. Let T be a set of integers from which share tokens are chosen. Then the cumulative array C

is the assignment of m share tokens si 2 T to each participant Pi 2 P according
to the following table:
		M			Bm
				B1 B2
			A1 A2		Am
				s1 s2		sm
		P1	b1;1 b1;2			b1;m
		P2	b2;1 b2;2 b2;m
					.
					.
					.
		Pn	bn;1 bn;2		bn;m
The entries bi;j are binary and
bi;j =	1 if Pi 2 Aj
	( 0 otherwise

The participant Pi gets a share Si = fsjjbi;j = 1g for i = 1; : : : ; n.

In our example (P1; P2; P3; P4) = cl(P1P2 +P3P4 ) and its dual access struc-

ture is = cl(ffP1; P3g, fP1; P4g, fP2; P3g, fP2; P4gg). A Boolean function associated with is (P1; P2; P3; P4) = P1P3+ P1P4+ P2P3+ P2P4. The

cumulative matrix C takes the following form:

set P

336 9 SECRET SHARING

	P1P3 P1P4 P2P3 P2P4
	s1	s2	s3	s4
P1	1	1	0	0
P2	0	0	1	1
P3	1	0	1	0
P4	0	1	0	1

which assigns P1 the share fs1; s2g, P2 { the share fs3; s4g, P3 { the share fs1; s3g, and nally P4 gets the share fs2; s4g.

An implementation of secret sharing with the access structure over the can be done in two steps:

1.Design a cumulative array C . The number m of products in the minimal form of (P1; : : : ; Pn) gives the number of share tokens.

2.For a given m, we design an (m; m) threshold scheme and the share tokens are distributed to the participants according to the cumulative array.

Clearly, for a given access structure, one would like to be sure that the cumulative array gives the smallest number of share tokens. This can be taken care by nding the minimal form of the Boolean function associated with [198]. There is also reasonable to expect a single participant to be given as few as possible share tokens.

In general, the cumulative array does not guarantee that the resulting secret sharing gives short shares. To illustrate the point, consider a (2; 3) threshold

scheme. = cl(ffP1; P2g, fP1; P3g, fP2; P3g, fP1; P2; P3gg). The Boolean functions are

(P1; P2; P3) = P1P2 + P1P3 + P2P3 + P1P2P3 = P1P2 + P1P3 + P2P3: and

(P1; P2; P3) = (P1 + P2)(P1 + P3)(P2 + P3) = P1P2 + P1P3 + P2P3:

The cumulative array C is:

	P1P2 P1P3 P2P3
	s1	s2	s3
P1	1	1	0
P2	1	0	1
P3	0	1	1

9.2 General Secret Sharing

337

Clearly, any two participants are able to recover all three tokens (and the secret). Any single one cannot as there is always a missing token. Note that for each participant, the share consists of two tokens. In contrast, the Shamir scheme that implements (2;3) sharing, requires a single share for each participant.

9.2.2 Benaloh-Leichter Construction

Benaloh and Leichter [24] also gave a simple construction for arbitrary monotone access structures. Their construction applies (t; t) threshold schemes.

Given a monotone access structure over the set P = fP1; : : : ; Png of n participants. A Boolean function (P1; : : : ; Pn) associated with the access structure is rst represented in the minimal disjunctive normal form. Let

(P1; : : : ; Pn) = X i

i=1

where i is a monomial of the degree ti. The construction uses threshold schemes (each for the given monomial i). All threshold schemes share the same secret k 2 K. The shares in threshold schemes are selected independently.

Consider an example. Let = cl(ffP1; P2; P3g;fP1; P4g; fP2; P4gg). The Boolean function (P1; P2; P3; P4) = P1P2P3+ P1P4+ P2P4. The rst monomial

P1P2P3 is of the degree 3 so the corresponding threshold scheme is (3; 3). P1 is assigned a share s1;1; P2 { a share s1;2 and P3 { a share (k s1;1 s1;2). The second and third monomials are of the degree 2 each so their threshold schemes are (2; 2). For the second threshold scheme, P1 gets a share s2;1 and P4 { a share (k s2;1). For the third threshold scheme, P2 obtains a share s3;1 and P4 { a share (k s3;1). In summary, the participants hold the following shares:

P1 7! fs1;1; s2;1g
P2 7! fs1;2; s3;1g	:
P3 7! fk s1;1 s1;2g
P4 7! fk s2;1; k s3;1g

Note that Pi possesses many shares (each share for di erent scheme to which Pi belongs). At the pooling time, participants submit their whole shares to the combiner who knowing the ordering of partial shares, is able to recreate the secret.

338 9 SECRET SHARING

9.3 Perfectness

The notion of perfect secret sharing is de ned as follows.

De nition 29. A secret sharing scheme over the access structure is perfect if for any subset of participants A, the entropy of the secret is

H(K		SA) =	H(K)	if	=
	j		( 0		A 2
				otherwise

where SA is a random variable representing the shares assigned to the set A of participants.

For a perfect secret sharing, shares held by participants must be at least as long as the secret as the following theorem asserts. Before we formulate the theorem, we simplify the notation for entropy. Given a set B P, then the entropy of their shares is denoted as H(B) instead of more precise H(SB) where SB is the random variable representing shares held by B.

Theorem 40. Given a perfect secret sharing. Then

H(P ) H(K);

where H(P ) is entropy of the share held by a participant P 2 P.

						B 2
Proof. Take a maximal unauthorized set						= that does not contain P or
2 B		B [		2
P =	. Clearly,		P		so the following two equations are true

H(KjB) = H(K) and H(KjB; P ) = 0:

Now we use the two equations to derive the requested inequality. We start from:

H(P ) H(P jB)							any side information decreases the entropy
= H(P; B)	H(B)						as H(P; B) = H(B) + H(P jB)
= H(K; P; B)			H(KjB; P) H(B)				as H(K; P; B) = H(B; P ) + H(KB; P )
= H(K; P; B)			H(B)				as H(KjB; P ) = 0
= H(K; P; B)			H(K; B) + H(KjB)				as H(K; B) = H(B) + H(KjB)
= H(K; P;	B	)		H(K;	B	) + H(K)	since H(KjB) = H(K)
H(K)							note that H(K; P; B) H(K; B) 0

The above sequence establishes the result. tu

Theorem 41. The (t; t) Karnin-Greene-Hellman threshold scheme is perfect.

9.3 Perfectness

339

Proof. Recall that (t

1) shares are selected randomly, uniformly and indepen-

dently from

p that is P (Si = si) =

1

for i = 1; : : : ; t

1 and S1; : : : ; St 1

Z

p

t 1

are independent random variables. The random variable St = K

i=1 Si.

Without loss

of

generality, assume that

we have t

1 random

variables

S1; S2; : : : ; St 2; St. Clearly, the rst (t

P

2) variables are independent. St is

independent as St = K

t 2 Si

St 1 includes St 1 that is independent from

S1; S2; : : : ; St 2.

tu

Pi=1

From Theorem 41, it is possible to conclude that both the cumulative array and the Benaloh-Leichter constructions produce perfect secret sharing schemes.

Consider the Shamir scheme. In our de nition, the dealer selects at random a polynomial f (x) of degree at most (t 1), that is Don chooses independently and uniformly at random coeÆcients a0; : : : ; at 1 from GF (p).

Theorem 42. The Shamir scheme based on a random polynomial f(x) = a0 + a1x+: : :+at 1xt 1 of degree at most (t 1) with ai 2R GF (p) for i = 0; : : : ; t 1 is perfect (the secret is a0 = k).

Proof. Assume that (t 1) shares have been made public. Without loss of generality, we assume that these shares are s1; : : : ; st 1. Thus the following system of equations can be written:

s1 = f (x1) = a0 + a1x1 + : : : + at 1x1t 1 s2 = f (x2) = a0 + a1x2 + : : : + at 1x2t 1

.

.

.

st 1 = f (xt 1) = a0 + a1xt 1 + : : : + at 1xtt 11

The system includes (t 1) linear equations with t unknown. The best we can do is to select one of the unknowns, say a0, and express other unknowns as linear combinations of a0. The uncertainty about the secret is not diminished. This means that the Shamir secret sharing is perfect. ut

The Blakley (t; n) threshold scheme is also perfect. A set of (t 1) participants can identify collectively a line containing the secret (a point on the line). On the other hand, a single participant may try to guess the line and than nd the secret. In both cases, the chances of getting the correct secret (point) are the same.

340 9 SECRET SHARING

Secret sharing schemes can be constructed using geometrical, algebraic or combinatorial structures for which there is a well-de ned critical set of elements, which allows to recover the whole structure (and the secret). It could be argued that perfect secret sharing scheme are equivalent to orthogonal arrays (for the de nition consult [499]). There are also nonperfect schemes that can be constructed using such combinatorial structures such as Latin squares, room squares, cycle systems, etc.

9.4 Information Rate

Recall that, in perfect secret sharing, any participant must hold a share at least as long as the secret. Participants typically insist on having shares are short as possible. Clearly, shorter shares are easier to manipulate, require less storage, and consume smaller communication overhead. Also shorter shares are easier to protect. Therefore, the length of shares assigned to each participant by the dealer is widely considered as the most important eÆciency measures of secret sharing. These measures are also called the information rates.

De nition 30. Assume there is a secret sharing scheme with its dealer function D : K ! S1 S2 Sn over the access structure . The information rate for Pi 2 P is

H(K)i = H(Si)

where H(Si) is the entropy of the share of Pi (or more precisely, the entropy of random variable Si that represents uncertainty of the share assigned to Pi). The average information rate of the scheme is

1 n

~ = n Xi=1 i:

The information rate of the scheme is

= min i:

i=1;:::;n

According to Theorem 40, we can say that i 1 for every participant Pi 2 P. As ~ is the average over all participants, then obviously ~ 1. The information rates satisfy the relation

0 ~ 1: