IACR News item: 26 October 2015
Allison Bishop, Valerio Pastro, Rajmohan Rajaraman, Daniel Wichs
ePrint ReportIn this scenario, to share an $m$-bit message with a reconstruction failure probability of at most $2^{-k}$, a known lower-bound shows that the share size must be at least $m + k$ bits. On the other hand, all prior constructions have share size that scales linearly with the number of parties $n$, and the prior state-of-the-art scheme due to Cevallos et al. (EUROCRYPT \'12) achieves $m + \\widetilde{O}(k + n)$.
In this work, we construct the first robust secret sharing scheme in the maximal corruption setting with $n=2t+1$, that avoids the linear dependence between share size and the number of parties $n$. In particular, we get a share size of only $m + \\widetilde{O}(k)$ bits. Our scheme is computationally efficient and relies on approximation algorithms for the minimum graph bisection problem.
Additional news items may be found on the IACR news page.