Efficient robust secret sharing from expander graphs

摘要

AbstractThreshold secret sharing allows a dealer to share a secret amongnplayers so that any coalition oftplayers learns nothing about the secret, but anyt+1 players can reconstruct the secret in its entirety. Robust secret sharing (RSS) provides the additional guarantee that even iftmalicious players mangle their shares, they cannot cause the honest players to reconstruct an incorrect secret. In this work, we construct a simple RSS protocol fort=12−ğœ–n$t = left ({ rac {1}{2} - epsilon }ight )n$that achieves logarithmic overhead in terms of share size and simultaneously allows efficient reconstruction. Our shares size increases by an additive term ofO(κ+logn)$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 thenplayers as nodes in an expander graph, each player only checks its neighbors in the expander graph.