Hybrid-Secure MPC: Trading Information-Theoretic Robustness for Computational Privacy

Christoph Lucas; Dominik Raub; Ueli Maurer

Paper 2009/009

Hybrid-Secure MPC: Trading Information-Theoretic Robustness for Computational Privacy

Christoph Lucas, Dominik Raub, and Ueli Maurer

Abstract

Most protocols for distributed, fault-tolerant computation, or multi-party computation (MPC), provide security guarantees in an all-or-nothing fashion: If the number of corrupted parties is below a certain threshold, these protocols provide all specified security guarantees. Beyond this threshold, they provide no security guarantees at all. Furthermore, most previous protocols achieve either information-theoretic (IT) security, in which case this threshold is low, or they achieve only computational security, in which case this threshold is high. In contrast, a hybrid-secure protocol provides different security guarantees depending on the set of corrupted parties and the computational power of the adversary, without being aware of the actual adversarial setting. Thus, hybrid-secure MPC protocols allow for graceful degradation of security. We present a hybrid-secure MPC protocol that provides an optimal trade-off between IT robustness and computational privacy: For any robustness parameter r<n/2, we obtain one MPC protocol that is simultaneously IT secure with robustness for up to t<=r actively corrupted parties, IT secure with fairness (no robustness) for up to t<n/2, and computationally secure with agreement on abort (privacy and correctness only) for up to t<n-r. Our construction is secure in the universal composability (UC) framework (based on a network of secure channels, a broadcast channel, and a common reference string). It achieves the bound on the trade-off between robustness and privacy shown by Ishai et al. [CRYPTO'06] and Katz [STOC'07], the bound on fairness shown by Cleve [STOC'86], and the bound on IT security shown by Kilian [STOC'00], and is the first protocol that achieves all these bounds simultaneously. For example, in the special case r=0 our protocol simultaneously achieves non-robust MPC for up to t<n corrupted parties in the computational setting (like Goldreich et al. [STOC'87]), while providing security with fairness in the IT setting for up to t<n/2 corrupted parties (like Rabin and Ben-Or [STOC'89] though without robustness).

Note: Revised as paper underwent restructuring and cleanup.

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. Extended Abstract of this paper appears in PODC 2010
Keywords: Multi-party computation information-theoretic security computational security hybrid security universal composability party emulation
Contact author(s): raub @ cs au dk
History: 2011-03-02: last of 6 revisions; 2009-01-12: received; See all versions
Short URL: https://ia.cr/2009/009
License: CC BY

BibTeX

@misc{cryptoeprint:2009/009,
      author = {Christoph Lucas and Dominik Raub and Ueli Maurer},
      title = {Hybrid-Secure MPC: Trading Information-Theoretic Robustness for Computational Privacy},
      howpublished = {Cryptology ePrint Archive, Paper 2009/009},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/009}},
      url = {https://eprint.iacr.org/2009/009}
}