Secret sharing schemes are multi-party protocols related to key establishment. The original motivation for secret sharing was the following. To safeguard cryptographic keys from loss, it is desirable to create backup copies. The greater the number of copies made, the greater the risk of security exposure; the smaller the number, the greater the risk that all are lost. Secret sharing schemes address this issue by allowing enhanced reliability without increased risk. They also facilitate distributed trust or shared control for critical activities (e.g., signing corporate cheques; opening bank vaults), by gating the critical action on cooperation by t of n users.
The idea of secret sharing is to start with a secret, and divide it into pieces called shares which are distributed amongst users such that the pooled shares of specific subsets of users allow reconstruction of the original secret. This may be viewed as a key pre-distribution technique, facilitating one-time key establishment, wherein the recovered key is pre-deter- mined (static), and, in the basic case, the same for all groups.
A secret sharing scheme may serve as a shared control scheme if inputs (shares) from two or more users are required to enable a critical action (perhaps the recovered key allows this action to trigger, or the recovery itself is the critical action). In what follows, simple shared-control schemes introduced in § 12.7.1 are a subset of threshold schemes discussed in §12.7.2, which are themselves a subclass of generalized secret sharing schemes as described in §12.7.3.
Simple shared control schemes
(i) Dual control by modular addition
If a secret number S, 0 < S < in-1 for some integer m, must be entered into a device (e.g., a seed key), but for operational reasons, it is undesirable that any single individual (other than a trusted party) know this number, the following scheme may be used. A trusted party T generates a random number 1 < Si < m -1, and gives the values Sj and S-Si mod m to two parties A and B, respectively. A and В then separately enter their values into the device, which sums them modulo rn to recover 5. If A and В are trusted not to collude, then neither one has any information about 5, since the value each possesses is a random number between 0 and m -1. This is an example of a split-knowledge scheme - knowledge of the secret S is split among two people. Any action requiring 5 is said to be under dual control - two people are required to trigger it.
(ii) Unanimous consent control by modular addition
The dual control scheme above is easily generalized so that the secret S may be divided among t users, all of whom are required in order to recover S, as follows: T generates t — 1 independent random numbers 5,, 0 < S, < m— 1, 1 < i < t — 1. Parties P through Pt-i are given 5,, while Pt is given St = S — X^=i Si mod m. The secret is recovered as 5 = X)i=i mo(l w- Both here and in the dual control scheme above, modulo m operations may be replaced by exclusive-OR, using data values S and St of fixed bit-length lg(m).
12.68 Remark (technique for splitting keys) The individual key components in a split control scheme should be full-length. This provides greater security than partitioning an r-bit key into t pieces of r/t bits each. For example, for r = 56 and f = 2, if two parties are each given 28 bits of the key, exhaustive search by one party requires only 228 trials, while if each party is given a 56-bit piece, 256 trials are necessary.