Perfectly-Secure Graph-Based Distributed Secret Sharing Protocols

A Distributed Secret Sharing Protocol (DSSP) enables a dealer to distribute multiple secrets among a set of users by placing shares on storage nodes scattered across a public network, so that each user can reconstruct exactly one secret by accessing its designated nodes. Two security notions are considered: weak secrecy, which prevents a user from learning any other individual secret, and perfect secrecy, which prevents a user from gaining any information about the collection of all other secrets. We study perfectly-secure graph-based DSSPs, where each user accesses exactly two storage nodes. We determine the exact optimal storage overhead for trees, stars, paths, cycles, and complete graphs, and provide matching constructions. For arbitrary graphs, we present a decomposition construction that uses protocols on simpler subgraphs as building blocks. Our results show that perfect secrecy has no additional storage cost over weak secrecy for acyclic graphs, while it strictly increases the overhead for graphs containing cycles.