You are looking at a specific version 20130822:204059 of this paper. See the latest version.

Paper 2013/349

A Dynamic Tradeoff Between Active and Passive Corruptions in Secure Multi-Party Computation

Martin Hirt and Christoph Lucas and Ueli Maurer

Abstract

At STOC '87, Goldreich et al.~presented two protocols for secure multi-party computation (MPC) among $n$ parties: The first protocol provides \emph{passive} security against $t<n$ corrupted parties. The second protocol provides even \emph{active} security, but only against $t<n/2$ corrupted parties. Although these protocols provide security against the provably highest possible number of corruptions, each of them has its limitation: The first protocol is rendered completely insecure in presence of a single active corruption, and the second protocol is rendered completely insecure in presence of $\lceil n/2 \rceil$ passive corruptions. At Crypto 2006, Ishai et al.~combined these two protocols into a single protocol which provides passive security against $t<n$ corruptions and active security against $t<n/2$ corruptions. This protocol unifies the security guarantees of the passive world and the active world (``best of both worlds''). However, the corruption threshold $t<n$ can be tolerated only when \emph{all} corruptions are passive. With a single active corruption, the threshold is reduced to $t<n/2$. As our main result, we introduce a \emph{dynamic tradeoff} between active and passive corruptions: We present a protocol which provides security against $t<n$ passive corruptions, against $t<n/2$ active corruptions, \emph{and everything in between}. In particular, our protocol provides full security against $k$ active corruptions, as long as less than $n-k$ parties are corrupted in total, for any unknown $k$. The main technical contribution is a new secret sharing scheme that, in the reconstruction phase, releases secrecy \emph{gradually}. This allows to construct non-robust MPC protocols which, in case of an abort, still provide some level of secrecy. Furthermore, using similar techniques, we also construct protocols for reactive MPC with hybrid security, i.e., different thresholds for secrecy, correctness, robustness, and fairness. Intuitively, the more corrupted parties, the less security is guaranteed.

Note: The order of the author names was unintentionally wrong.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. IACR version of a Crypto 2013 paper
Keywords
Multi-party computationgradual secret sharingcomputational securitymixed adversary
Contact author(s)
hirt @ inf ethz ch
History
2013-08-22: revised
2013-06-10: received
See all versions
Short URL
https://ia.cr/2013/349
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.