  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 provides the strongest security guarantees and
remains secure even against computationally unbounded adversaries.
Perfectly-secure MPC protocols is a class of information-theoretically secure
MPC protocols, which provides 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 protocol is possible as
long as adversary can corrupt any $t_s < n/3$ parties. On the other hand,
perfectly-secure asynchronous MPC protocol 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 and 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.
