A novel information theoretic approach to solving secret sharing problem

A novel information theoretic approach is proposed to solve the secret sharing problem, in which a dealer distributes one or multiple secrets among a set of participants in such a manner that for each secret only qualified sets of users can recover this secret by pooling their shares together while non-qualified sets of users obtain no information about the secret even if they pool their shares together. While existing secret sharing systems (implicitly) assume that communications between the dealer and participants are noiseless, this paper takes a more practical assumption that the dealer delivers shares to the participants via a noisy broadcast channel.

Thus, in contrast to the existing solutions that are mainly based on number theoretic tools, an information theoretic approach is proposed, which exploits the channel randomness during delivery of shares as additional resources to achieve secret sharing requirements. In this way, secret sharing problems can be reformulated as equivalent secure communication problems via wiretap channel models, and can hence be solved by employing powerful information theoretic security techniques. This approach is first developed for the classic secret sharing problem, in which only one secret is to be shared. This classic problem is shown to be equivalent to a communication problem over a compound wiretap channel. Thus, the lower and upper bounds on the secrecy capacity of the compound channel provide the corresponding bounds on the secret sharing rate, and the secrecy scheme designed for the compound channel provides the secret sharing schemes.

The power of the approach is further demonstrated by a more general layered multi-secret sharing problem, which is shown to be equivalent to the degraded broadcast multiple-input multiple-output (MIMO) channel with layered decoding and secrecy constraints. The secrecy capacity region for the degraded MIMO broadcast channel is characterized, which provides the secret sharing capacity region. Furthermore, the secure encoding scheme that achieves the secrecy capacity region providesan information theoretic scheme for sharing the secrets

In the classic secret sharing problem, a dealer intends to distribute a secret among a set of participants such that only qualified sets of participants can correctly recover the secret by pooling their shares together, while the non-qualified set of participants obtain no information about the secret even if they pool their shares together. There are rich applications of secret sharing including construction of protocols and algorithms for secure multiparty computations [3, 4], Byzatine agreement [5], threshold cryptography [6], access control [7],attribute-based encryption [8], and generalized oblivious transfer [9]. The existing solutions for the secret sharing problems are mainly based on the number theoretic tools, in which contents of the shares that the dealer delivers to the participants are specially designed in order to guarantee the secret sharing requirements. While such approaches work well for simple secret sharing problems, they are not readily extendable to more complicated problems, in which qualified and non-qualified sets become more complicated, and/or multiple secrets are simultaneously shared. 

We consider the following secret sharing problem. Suppose the system consists of a dealer and a set of participants P = {1, 2, · · · , K}. The dealer has a secret W (taken from a set W) for the K participants to share. We define an access structure A, which contains all subsets of P that are required to recover the secret. Each set A ∈ A is called a qualified set. We assume that the access structure considered in this paper is monotone [19], that is if A ∈ A and A ⊆ A1, then A1 ∈ A. For the secret sharing scheme, we require that if the users in any qualified set A ∈ A gather their observations together, then they can recover the secret with a negligible error probability. We define a non-access structure B such that for any set B 6∈ B, we require that even if users in the set B gather their observations together, they obtain negligible information about the secret message. In many applications, B = AC. In the existing secret sharing schemes, the communications between the dealer and participants are assumed to be noiseless as the classic secret sharing problem does not involve channel. In this paper, we assume that the dealer and the participants are connected by a noisy broadcast channel, as shown in Figure 1. If the dealer transmits Xn , participant k receives Y n k , and the relationship among the input and outputs is characterized by the transition probability distribution