Valerio Pastro: Essentially Optimal Robust Secret Sharing with Maximal Corruptions

Speaker: Valerio Pastro

Date: Friday, April 29, 2016

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: Hewlett, G882

Event Type:

Room Description:

Host: Vinod Vaikuntanathan

Contact: Deborah Lehto, 617.324.7303,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: Valerio Pastro: Essentially Optimal Robust Secret Sharing with Maximal Corruptions


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

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security (CIS) Seminar Series 2016.

Created by Deborah Goodwin Email at Friday, April 01, 2016 at 10:48 AM.