Paper 2016/735
Efficient Robust Secret Sharing from Expander Graphs
Brett Hemenway and Rafail Ostrovsky
Abstract
Threshold secret sharing is a protocol that 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. When $t < \frac{n}{3}$, Shamir sharing is known to be robust, and when $t > \frac{n}{2}$, RSS is known to be impossible, but for $\frac{n}{3} < t < \frac{n}{2}$ much less is known. When $\frac{n}{3} < t < \frac{n}{2}$ previous RSS protocols could either achieve optimal share size with inefficient (exponential time) reconstruction procedures, or suboptimal share size with polynomial time reconstruction. 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 $O(\kappa + \log n)$, and reconstruction succeeds except with probability at most $2^{\kappa}$. This provides a partial solution to a problem posed by Cevallos et al. in Eurocrypt 2012. Namely, when $t = \left( \frac{1}{2}  O(1) \right)n$ we show that the share size in RSS schemes do not require an overhead that is linear in $n$. Previous efficient RSS protocols like that of Rabin and BenOr (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. When $t = \left\{ \frac{1}{2}  O(1) \right\}n$, the concurrent, independent work of Cramer et al. (Eurocrypt '15) shows how to achieve shares that \emph{decrease} with the number of players using completely different techniques.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Robust Secret SharingExpander GraphsSecure Message Transmission
 Contact author(s)
 fbrett @ cis upenn edu
 History
 20160729: revised
 20160728: received
 See all versions
 Short URL
 https://ia.cr/2016/735
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/735, author = {Brett Hemenway and Rafail Ostrovsky}, title = {Efficient Robust Secret Sharing from Expander Graphs}, howpublished = {Cryptology ePrint Archive, Paper 2016/735}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/735}}, url = {https://eprint.iacr.org/2016/735} }