International Association
for Cryptologic Research

We consider the task of designing secure computation protocols in an unstable network where honest parties can drop out at any time, according to a schedule provided by the adversary. This type of setting, where even honest parties are prone to failures, is more realistic than traditional models, and has therefore gained a lot of attention recently. Unlike previous works in the literature, we allow parties to return to the computation according to an adversarially chosen schedule and, moreover, we do not assume that these parties receive the messages that were sent to them while being offline. However, we do assume an upper bound on the number of rounds that an honest party can be off-line---otherwise protocols in this setting cannot guarantee termination within a bounded number of rounds.

We study the settings of perfect, statistical and computational security and design MPC protocols in each of these scenarios. We assume that the intersection of online-and-honest parties from one round to the next is at least $2t+1$, $t+1$ and $1$ respectively, where $t$ is the number of (actively) corrupt parties. We show the intersection requirements to be optimal. Our (positive) results are obtained in a way that may be of independent interest: we implement a traditional stable network on top of the unstable one, which allows us to plug in \textit{any} MPC protocol on top. This approach adds a necessary overhead to the round count of the protocols, which is related to the maximal number of rounds an honest party can be offline. We also present a novel, perfectly secure MPC protocol that avoids this overhead by following a more ``direct'' approach rather than building a stable network on top. We introduce our network model in the UC-framework and prove the security of our protocols within this setting.