Efficient Secret Sharing Schemes Achieving Optimal Information Rate

One of the important problems in secret sharing schemes is to establish bounds on the size of the shares to be given to participants in secret sharing schemes. The other important problem in secret sharing schemes is to reduce the computational complexity in both secret distribution phase and secret reconstruction phase. In this paper, we design efficient threshold (n,k) secret sharing schemes to achieve both of the above goals. In particular, we show that if the secret size vertical bar s vertical bar is larger than max {1 + log(2) n, n(n - k)/(n - 1)} then ideal secret sharing schemes exist. In the efficient ideal secret sharing schemes that we will construct, only XOR-operations on binary strings are required (which is the best we could achieve). These schemes will have many applications both in practice and in theory. For example, they could be used to design very efficient verifiable secret sharing schemes which will have broad applications in secure multi-party computation and could be used to design efficient privacy preserving data storage in cloud systems.