# On the Cost of Reconstructing a Secret, or {VSS} with Optimal Reconstruction Phase

## Ronald Cramer and Ivan Damg{å}rd and Serge Fehr

```
```Consider a scenario where an $l$-bit secret has been distributed
among $n$ players
by an honest dealer using some
secret sharing scheme. Then, if all players behave
honestly, the secret can be
reconstructed in one round with zero error probability, and by broadcasting $nl$ bits.

We ask the following question: how close to this ideal can we get if up to
$t$ players (but not the dealer) are corrupted by an adaptive, active adversary with unbounded
computing power? - and where in addition we of course require that the adversary does not
learn the secret ahead of reconstruction time. It is easy to see that
$t= \lfloor (n-1)/2 \rfloor$ is the maximal value of $t$ that can be tolerated,
and furthermore, we show that
the best we can hope for is a one-round reconstruction protocol where every honest player
outputs the correct secret or ``failure''. For any such protocol with failure probability
at most $2^{-\Omega(k)}$,
we show a lower bound of $\Omega(nl + k n^2)$ bits
on the information communicated. We further show that this is tight up to a constant factor.

The lower bound trivially applies as well to VSS
schemes, where also the dealer may be corrupt. Using generic methods, the scheme
establishing the upper bound can be turned into a VSS with efficient reconstruction. \linebreak However,
the distribution phase becomes very inefficient. Closing this gap, we present a new VSS
protocol where the distribution complexity matches that of the previously best
known VSS, but where the reconstruction phase meets our lower bound up to a constant
factor.
The reconstruction is a factor of $n$ better than previous
VSS protocols. We show an
application of this to multi-party computation with pre-processing,
improving the complexity of
earlier similar protocols by a factor of $n$.