Paper 2013/529

How to Withstand Mobile Virus Attacks, Revisited

Joshua Baron and Karim El Defrawy and Joshua Lampkins and Rafail Ostrovsky

Abstract

Secure Multiparty Computation (MPC) protocols allow a set of distrusting participants to securely compute a joint function of their private inputs without revealing anything but the output of the function to each other. In 1991 Ostrovsky and Yung introduced the \emph{proactive security model}, where faults spread throughout the network, analogous to the spread of a virus or a worm. More specifically, in the proactive security model, the adversary is not limited in the number of parties it can corrupt but rather in the {\em rate} of corruption with respect to a ``rebooting'' rate. In the same paper, Ostrovsky and Yung showed that constructing a general purpose MPC protocol in the proactive security model is indeed feasible when the rate of corruption is a constant fraction of the parties. Their result, however, was shown only for stand-alone security and incurred a large polynomial communication overhead for each gate of the computation. In contrast, protocols for ``classical'' MPC models (where the adversary is limited to corrupt in total up to a fixed fraction of the parties) have seen dramatic progress in reducing communication complexity in recent years. The question that we consider in this paper is whether continuous improvements of communication overhead in protocols for the ``classical'' stationary corruptions model in the MPC literature can lead to communication complexity reductions in the proactive security model as well. It turns out that improving communication complexity of proactive MPC protocols using modern techniques encounters two fundamental roadblocks due to the nature of the mobile faults model: First, in the proactive security model there is the inherent impossibility of ``bulk pre-computation'' to generate cryptographic material that can be slowly consumed during protocol computation in order to amortize communication cost (the adversary can easily discover pre-computed values if they are not refreshed, and refreshing is expensive); second, there is an apparent need for double-sharing (which requires high communication overhead) of data in order to achieve proactive security guarantees. Thus, techniques that were used to speed up classical MPC do not work, and new ideas are needed. That is exactly what we do in this paper: we show a novel MPC protocol in the proactive security model that can tolerate a $\frac13-\epsilon$ (resp. $\frac12-\epsilon$) fraction of moving faults, is perfectly (resp. statistically) UC-secure, and achieves near-linear communication complexity for each step of the computation. Our results match the asymptotic communication complexity of the best known results in the ``classical'' model of stationary faults \cite{DIK10}. One of the important building blocks that we introduce is a new near-linear ``packed'' proactive secret sharing (PPSS) scheme, where the amortized communication and computational cost of maintaining each individual secret share is just a constant. We believe that our PPSS scheme might be of independent interest.

Note: Editing email of third author.