Paper 2011/094

Graceful Degradation in Multi-Party Computation

Martin Hirt, Christoph Lucas, Ueli Maurer, and Dominik Raub

Abstract

The goal of \emph{Multi-Party Computation} (MPC) is to perform an arbitrary computation in a distributed, private, and fault-tolerant way. For this purpose, a fixed set of $n$ parties runs a protocol that tolerates an adversary corrupting a subset of the participating parties, and still preserves certain security guarantees. Most MPC protocols provide security guarantees in an \emph{all-or-nothing} fashion: Either the set of corrupted parties is tolerated and the protocol provides all specified security guarantees, or the set of corrupted parties is not tolerated and the protocol provides no security guarantees at all. Similarly, corruptions are in an all-or-nothing fashion: Either a party is fully honest, or it is fully corrupted. For example, an actively secure protocol is rendered completely insecure when just one party is corrupted additionally to what is tolerated, even if all corrupted parties are only passive. In this paper, we provide the first treatment of MPC with graceful degradation of both security and corruptions. First of all, our protocols provide graceful degradation of security, i.e., different security guarantees depending on the actual number of corrupted parties: the more corruptions, the weaker the security guarantee. We consider all security properties generally discussed in the literature (secrecy, correctness, robustness, fairness, and agreement on abort). Furthermore, the protocols provide graceful degradation with respect to the corruption type, by distinguishing fully honest parties, passively corrupted parties, and actively corrupted parties. Security can be maintained against more passive corruptions than is possible for active corruptions. We focus on perfect security, and prove exact bounds for which MPC with graceful degradation of security and corruptions is possible for both threshold and general adversaries. Furthermore, we provide protocols that meet these bounds. This strictly generalizes known results on hybrid security and mixed adversaries.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Full version of a paper appearing at ICITS 2011
Keywords
Multi-party computationgraceful degradationhybrid securitymixed adversaries.
Contact author(s)
clucas @ inf ethz ch
History
2011-02-28: received
Short URL
https://ia.cr/2011/094
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/094,
      author = {Martin Hirt and Christoph Lucas and Ueli Maurer and Dominik Raub},
      title = {Graceful Degradation in Multi-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2011/094},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/094}},
      url = {https://eprint.iacr.org/2011/094}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.