Perfectly-Secure Synchronous MPC With Asynchronous Fallback Guarantees

Secure
multi-party computation
(MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of
$n$
mutually distrusting parties to carry out any joint computation of their private inputs, without disclosing any additional information about their inputs. MPC with
information-theoretic
security (also called
unconditional security
) provides the strongest security guarantees and remains secure even against
computationally unbounded
adversaries.
Perfectly-secure
MPC protocols are a class of information-theoretically secure MPC protocols, which provide all the security guarantees in an
error-free
fashion. The focus of this work is perfectly-secure MPC. Known protocols are designed
assuming
either a
synchronous
or
asynchronous
communication network. It is well known that perfectly-secure
synchronous
MPC is possible as long as the adversary can corrupt any
$t_{s} < n/3$
parties. On the other hand, perfectly-secure
asynchronous
MPC protocols can tolerate up to
$t_{a} < n/4$
corrupt parties. A natural question is does there exist a
single
MPC protocol for the setting where the parties are
not aware
of the exact network type and which can tolerate up to
$t_{s} < n/3$
corruptions in a synchronous network and up to
$t_{a} < n/4$
corruptions in an
asynchronous
network. We design such a
best-of-both-worlds
perfectly-secure MPC protocol, provided
$3t_{s} + t_{a} < n$
holds. For designing our protocol, we design two important building blocks which are of independent interest. The first building block is a best-of-both-worlds
Byzantine agreement
(BA) protocol tolerating
$t < n/3$
corruptions which remains secure
both
in a synchronous as well as asynchronous network. The second building block is a polynomial-based best-of-both-worlds
verifiable secret-sharing
(VSS) protocol, which can tolerate up to
$t_{s}$
and
$t_{a}$
corruptions in a
synchronous
and in an
asynchronous
network respectively.