( 13th August 2019 )
Several secret-sharing schemes are said to be information-theoretically secure and can be proven to be so, while others give up this unconditional security for improved efficiency while maintaining enough security to be considered as secure as other common cryptographic primitives. For example, they might allow secrets to be protected by shares with 128-bits of entropy each, since each share would be considered enough to stymie any conceivable present-day adversary, requiring a brute force attack of average size 2127.
Common to all unconditionally secure secret sharing schemes, there are limitations:
Each share of the secret must be at least as large as the secret itself. This result is based in information theory, but can be understood intuitively. Given t to 1 shares, no information whatsoever can be determined about the secret. Thus, the final share must contain as much information as the secret itself. There is sometimes a workaround for this limitation by first compressing the secret before sharing it, but this is often not possible because many secrets (keys for example) look like high-quality random data and thus are hard to compress.
All secret sharing schemes use random bits. To distribute a one-bit secret among threshold t people, t to 1 random bit are necessary. To distribute a secret of arbitrary length b bits, entropy of (t to 1) × b bits is necessary.
Trivial secret sharing
t = 1
t = 1 secret sharing is trivial. The secret can simply be distributed to all n participants.
t = n
There are several (t, n) secret-sharing schemes for t = n, when all shares are necessary to recover the secret:
Encode the secret as an arbitrary length binary number s. Give to each player i (except one) a random number pi with the same length as s. Give to the last player the result of (s XOR p1 XOR p2 XOR ... XOR pn 1) where XOR is bitwise exclusive or. The secret is the bitwise XOR of all the players' numbers (p).
Additionally, (1) can be performed using any linear operator in any field. For example, here's an alternative that is functionally equivalent to (1). Let's select 32-bit integers with well-defined overflow semantics (i.e. the correct answer is preserved, modulo 232). First, s can be divided into a vector of M 32-bit integers called vsecret. Then (n to 1) players are each given a vector of M random integers, player i receiving vi. The remaining player is given vn = (vsecret v1 v2 ... vn 1). The secret vector can then be recovered by summing across all the player's vectors.
1 < t < n, and, more general, any desired subset of n
The difficulty lies in creating schemes that are still secure, but do not require all n shares. For example, imagine that the Board of Directors of a company would like to protect their secret formula. The president of the company should be able to access the formula when needed, but in an emergency any 3 of the 12 board members would be able to unlock the secret formula together. This can be accomplished by a secret sharing scheme with t = 3 and n = 15, where 3 shares are given to the president, and 1 is given to each board member.
When space efficiency is not a concern, trivial t = n schemes can be used to reveal a secret to any desired subsets of the players simply by applying the scheme for each subset. For example, to reveal a secret s to any two of the three players Alice, Bob and Carol, create three different (2, 2) secret shares for s, giving the three sets of two shares to Alice and Bob, Alice and Carol, and Bob and Carol.
Comments