  We initiate the study of the network agnostic MPC protocols with statistical
security. Network agnostic protocols give the best possible security guarantees
irrespective of the underlying network type. We consider the general-adversary
model, where the adversary is characterized by an adversary structure which
enumerates all possible candidate subsets of corrupt parties. The
$\mathcal{Q}^{(k)}$ condition enforces that the union of no $k$ subsets from
the adversary structure covers the party set. Given an unconditionally-secure
PKI setup, known statistically-secure synchronous MPC protocols are secure
against adversary structures satisfying the $\mathcal{Q}^{(2)}$ condition.
Known statistically-secure asynchronous MPC protocols can tolerate
$\mathcal{Q}^{(3)}$ adversary structures. Fix a set of $n$ parties $\mathcal{P}
= \{P_1, ... ,P_n\}$ and adversary structures $\mathcal{Z}_s$ and
$\mathcal{Z}_a$, satisfying the $\mathcal{Q}^{(2)}$ and $\mathcal{Q}^{(3)}$
conditions respectively, where $\mathcal{Z}_a \subset \mathcal{Z}_s$. Then,
given an unconditionally-secure PKI, we ask whether it is possible to design a
statistically-secure MPC protocol resilient against $\mathcal{Z}_s$ and
$\mathcal{Z}_a$ in a synchronous and an asynchronous network respectively if
the parties in $\mathcal{P}$ are unaware of the network type. We show that it
is possible iff $\mathcal{Z}_s$ and $\mathcal{Z}_a$ satisfy the
$\mathcal{Q}^{(2,1)}$ condition, meaning that the union of any two subsets from
$\mathcal{Z}_s$ and any one subset from $\mathcal{Z}_a$ is a proper subset of
$\mathcal{P}$. We design several important network agnostic building blocks
with the $\mathcal{Q}^{(2,1)}$ condition, such as Byzantine broadcast,
Byzantine agreement, information checking protocol, verifiable secret-sharing
and secure multiplication protocol, whose complexity is polynomial in $n$ and
$|\mathcal{Z}_s|$.
