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)

Abstract:

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

Categories: E.3