Lower bounds for robust secret sharing schemes

A (k, n, epsilon) robust secret sharing scheme permits a secret to be shared among a set P of n participants in such a way that only subsets of P of size at least k can recover the secret, but any subsets of less than k participants have absolutely no information on the secret. Moreover, any coalition of less than k participants, called cheaters, has probability of successful cheating less than epsilon. In this paper we provide new bounds on the information distributed to participant in any (k, n, epsilon) robust secret sharing scheme which relate the size of the shares, the size of the secret, the probability of cheating, and the probability of guessing. (C) 1997 Elsevier Science B.V.