New Results on Distributed Secret Sharing Protocols

A Distributed Secret Sharing Protocol (DSSP for short) allows a dealer to share multiple secrets among a set of users by storing the shares on storage nodes distributed over a public insecure network. Users can later download the shares from the nodes they can access, in order to reconstruct the secrets (each user is allowed to reconstruct exactly one secret). In this paper we propose three contributions: we first carefully analyze the security requirements for DSSPs and we show that if the shared secrets are statistically dependent, then no DSSP satisfying either the weak secrecy requirement or the perfect secrecy one can exist. Then, we propose two new definitions of security for DSSPs, which also take into account the statistical dependencies among the secrets. Afterwards, we consider DSSPs for a specific class of access structures, i.e., those which can be represented by a graph. In particular, we propose a protocol which can be used to share independent secrets having different sizes. The protocol can manage any kind of graph and generalizes previous protocols for secrets having the same sizes, while maintaining optimal storage requirements.