# On the Complexity of Verifiable Secret Sharing and Multiparty Computation

## Ronald Cramer and Ivan Damg{å}rd and Stefan Dziembowski

```
```We first study the problem of doing Verifiable Secret Sharing (VSS)
information theoretically secure for a general access structure. We do
it in the model where private channels between players and a broadcast
channel is given, and where an active, adaptive adversary can corrupt
any set of players not in the access structure. In particular, we
consider the complexity of protocols for this problem, as a function
of the access structure and the number of players. For all access
structures where VSS is possible at all, we show that, up t o a
polynomial time black-box reduction, the complexity of adaptively
secure VSS is the same as that of ordinary secret sharing (SS), where
security is only required against a passive, static adversary.
Previously, such a connection was only known for linear secret sharing
and VSS schemes. We then show an impossibility result indicating that
a similar equivalence does hot hold for Multiparty Computation (MPC):
we show that even if protocols are given black-box access for free to
an idealized secret sharing scheme secure for the access structure in
question, it is not possible to handle all relevant access structures
efficiently, not even if the adversary is passive and static. In
other words, general MPC can only be black-box reduced efficiently to
secret sharing if extra properties of the secret sharing scheme used
(such as linearity) are assumed.