Efficient robust secret sharing from expander graphs
Brett Hemenway, Rafail Ostrovsky
Abstract:
Threshold secret sharing allows a dealer to share a secret among n players so that any coalition of t players learns nothing about the secret, but any t+1 players can reconstruct the secret in its entirety. Robust secret sharing (RSS) provides the additional guarantee that even if t malicious players mangle their shares, they cannot cause the honest players to reconstruct an incorrect secret. In this work, we construct a simple RSS protocol for \(t = \left ({ \frac {1}{2} - \epsilon }\right )n\) that achieves logarithmic overhead in terms of share size and simultaneously allows efficient reconstruction. Our shares size increases by an additive term of \(\mathcal {O}(\kappa + \log n)\), and reconstruction succeeds except with probability at most 2âÎș. Previous efficient RSS protocols like that of Rabin and Ben-Or (STOC â89) and Cevallos et al. (Eurocrypt â12) use MACs to allow each player to check the shares of each other player in the protocol. These checks provide robustness, but require significant overhead in share size. Our construction identifies the n players as nodes in an expander graph, each player only checks its neighbors in the expander graph.
comment:
Cryptography and Communications 10(1): 79-99 (2018)
Fetch PDF file of the paper