Randomness in Multi-Secret Sharing Schemes
Carlo Blundo (Dipartimento di Informatica ed Applicazioni Università di Salerno, Italy)
Barbara Masucci (Dipartimento di Informatica ed Applicazioni Università di Salerno, Italy)
A multi-secret sharing scheme is a protocol to share a number of (arbitrarily related) secrets among a set of participants in such a way that only qualified sets of participants can recover the secrets, whereas non-qualified sets of participants might have partial information about them.
In this paper we analyze the amount of randomness needed by multi-secret sharing schemes. Given an m-tuple of access structures, we give a lower bound on the number of random bits needed by multi-secret sharing schemes; the lower bound is expressed in terms of a combinatorial parameter that depends only upon the access structures and not on the particular multi-secret sharing scheme used.
Keywords: cryptography, data security, randomness, secret sharing schemes