Key Management - Contemporary Cryptography - page 455

19.3 SECRET SHARING

As already mentioned above, there are situations in which it may be useful to split
a secret value (e.g., a cryptographic key) into multiple parts and to have different
parties hold and manage these parts. If, for example, one wants to have n parties
share a secret value s , then one can randomly choose n − 1 keys s 1 ,...,s n− 1 ,

compute

s n = s ⊕ s 1 ⊕ ... ⊕ s n− 1 ,

and distribute s 1 ,...,s n to the n parties. The secret value s can then only be
reconstructed if all n parties provide their parts. Consequently, such a secret splitting
system requires that all parties are available and reliable, and that they all behave
honestly in one way or another. If only one party is not available, loses its part, or
refuses to provide it, then the secret value s can no longer be reconstructed. Needless
to say, this is a major drawback and shortcoming of a secret splitting scheme and its
practicality.
In a secret sharing system , it is generally not required that all parties are
available and reliable, and that they all behave honestly. Instead, the reconstruction
of the secret value s requires only the parts of a well-defined subset of all parts
(in this case, the parts are called shares). More specifically, a secret sharing system
allows an entity, called the dealer, to share a secret value s among a set of n players,
P =

, such that only a qualified subset of the players can reconstruct
s from their shares. It is usually required that all nonqualified subsets of the players
get absolutely no information about s (as mentioned later, the secret sharing system
is then called perfect). The secret and the shares are usually elements of the same
domain, most often a finite field.
Formally, the set of qualified subsets is a subset of the power set 2 P and
is called the access structure Γ of the secret sharing system. If, for example,
Γ=

{ P 1 ,...,P n }

(i.e., only all players are qualified), then the secret sharing
system is a secret splitting system as described earlier. More generally, a k -out-of- n
secret sharing scheme can be defined as suggested in Definition 19.1.

{{ P 1 ,...,P n }}

Definition 19.1 ( K -out-of- n secret sharing system) A k -out-of- n secret sharing
scheme is a secret sharing system in which the access structure is

2 P Γ= { M ⊆ : | M |≥ k } .

1 players
who collaborate (and pool their shares) are not able to reconstruct s (or retrieve any
information about s ).

Furthermore, a k -out-of- n secret sharing scheme is perfect if k −