Valerio Pastro: Essentially Optimal Robust Secret Sharing with Maximal Corruptions

Abstract:

In a $t$-out-of-$n$ robust secret sharing scheme, a secret message is
shared among $n$ parties who can reconstruct the message by combining
their shares. An adversary can adaptively corrupt up to $t$ of the
parties, get their shares, and modify them arbitrarily. The scheme
should satisfy privacy, meaning that the adversary cannot learn
anything about the shared message, and robustness, meaning that the
adversary cannot cause the reconstruction procedure to output an
incorrect message. Such schemes are only possible in the case of an
honest majority, and here we focus on unconditional security in the
maximal corruption setting where $n = 2t+1$.

In 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.

Joint work with Allison Bishop, Rajmohan Rajaraman, and Daniel Wichs