Generalized secret sharing

The idea of a threshold scheme may be broadened to a generalized secret sharing scheme as follows. Given a set P of users, define Л (the access structure) to be a set of subsets, called the authorized subsets of P. Shares are computed and distributed such that the pooling of shares corresponding to any authorized subset A e A allows recovery of the secret S, but the pooling of shares corresponding to any unauthorized subset В CP, В £ A does not.

Threshold schemes are a special class of generalized secret sharing schemes, in which the access structure consists of precisely all f-subsets of users. An access structure is called monotone if, whenever a particular subset A of users is an authorized subset, then any subset of P containing A is also authorized. Monotone access structures are a requirement in many applications, and most natural schemes are monotone. Perfect secret sharing schemes have a monotone access structure as a consequence of the entropy formulation in Definition 12.73.

12.73 Definition A secret sharing scheme is perfect if the shares corresponding to each unauthorized subset provide absolutely no information, in the information-theoretic sense, about the shared secret (cf. Definition 12.69). More formally, where H denotes entropy (see §2.2.1), and A, В are sets of users using the above notation: H(SA) = 0 for any A e A, while

H(SB) = H(S) for any В f A.

The efficiency of a secret sharing scheme is measured by its information rate.

  • 12.74 Definition For secret sharing schemes, the information rate for a particular user is the bit- size ratio (size of the shared secret)/(size of that user’s share). The information rate for a secret sharing scheme itself is the minimum such rate over all users.
  • 12.75 Fact (perfect share bound) In any perfect secret sharing scheme the following holds for all user shares: (size of a user share) > (size of the shared secret). Consequently, all perfect secret sharing schemes must have information rate < 1.

Justification. If any user Pi had a share of bit-size less than that of the secret, knowledge of the shares (excepting that of P,) corresponding to any authorized set to which P, belonged, would reduce the uncertainty in the secret to at most that in Pfs share. Thus by definition, the scheme would not be perfect.

12.76 Definition Secret sharing schemes of rate 1 (see Definition 12.74) are called ideal.

As per Note 12.72, Shamir’s threshold scheme is an example of an ideal secret sharing scheme. Examples of access structures are known for which it has been proven that ideal schemes do not exist.

Secret sharing schemes with extended capabilities

Secret sharing schemes with a variety of extended capabilities exist, including:

  • 1. pre-positioned secret sharing schemes. All necessary secret information is put in place excepting a single (constant) share which must later be communicated, e.g., by broadcast, to activate the scheme.
  • 2. dynamic secret sharing schemes. These are pre-positioned schemes wherein the secrets reconstructed by various authorized subsets vary with the value of communicated activating shares.
  • 3. multi-secret threshold schemes. In these secret sharing schemes different secrets are associated with different authorized subsets.
  • 4. detection of cheaters, and verifiable secret sharing. These schemes respectively address cheating by one or more group members, and the distributor of the shares.

5. secret sharing with disenrollment. These schemes address the issue that when a secret share of a (t, n) threshold scheme is made public, it becomes a (t — 1, n) scheme.

< Prev   CONTENTS   Source   Next >