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).
Category / Keywords: Multi-party computation, information-theoretic security, computational security, hybrid security, universal composability, party emulation Publication Info: Extended Abstract of this paper appears in PODC 2010 Date: received 5 Jan 2009, last revised 2 Mar 2011 Contact author: raub at cs au dk Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: Revised as paper underwent restructuring and cleanup. Version: 20110302:090234 (All versions of this report) Discussion forum: Show discussion | Start new discussion