On identification secret sharing schemes

Abstract

Let ℘ be a set of participants sharing a secret from a set of secrets. A secret sharing scheme is a protocol such that any qualified subset of ℘ can determine the secret by pooling their shares, the messages which they receive, without error, whereas non-qualified subsets of ℘ cannot obtain any knowledge about the secret when they pool what they receive. In (optimal) schemes, the sizes of shared secrets depend on the sizes of shares given to the participants. Namely the former grow up exponentially as the latter increase exponentially. In this paper, instead of determining the secret, we require the qualified subsets of participants to identify the secret. This change would certainly make no difference from determining secret if no error for identification were allowed. So here we relax the requirement to identification such that an error may occur with a vanishing probability as the sizes of the secrets grow up. Under relaxed condition this changing allows us to share a set of secrets with double exponential size as the sizes of shares received by the participants exponentially grow. Thus much longer secret can be shared. On the other hand, by the continuity of Shannon entropy we have that the relaxation makes no difference for (ordinary) secret sharing schemes. We obtain the characterizations of relations of sizes of secrets and sizes of the shares for identification secret sharing schemes without and with public message. Our idea originates from Ahlswede-Dueck's awarded work in 1989, where the identification codes via channels were introduced. © 2003 Published by Elsevier Science (USA).