Paper 2013/529
How to Withstand Mobile Virus Attacks, Revisited
Joshua Baron, Karim El Defrawy, 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
Note: Editing email of third author.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Keywords
- proactive securitysecure multiparty computationsecret sharinglinear complexity
- Contact author(s)
- kmeldefrawy @ hrl com
- History
- 2013-09-10: last of 2 revisions
- 2013-08-30: received
- See all versions
- Short URL
- https://ia.cr/2013/529
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/529, author = {Joshua Baron and Karim El Defrawy and Joshua Lampkins and Rafail Ostrovsky}, title = {How to Withstand Mobile Virus Attacks, Revisited}, howpublished = {Cryptology {ePrint} Archive, Paper 2013/529}, year = {2013}, url = {https://eprint.iacr.org/2013/529} }