Multi-Party computation with omnipresent adversary

Ghodosi, Hossein, and Pieprzyk, Josef (2009) Multi-Party computation with omnipresent adversary. In: Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography: PKC '09 (5443) pp. 180-195. From: 12th International Conference on Practice and Theory in Public Key Cryptography, 18 - 20 March 2009, Irvine, CA, USA.

[img] PDF (Published Version)
Restricted to Repository staff only

PDF (Accepted Version) - Accepted Version
Download (188kB) | Preview
View at Publisher Website:


Secure multi-party computation (MPC) protocols enable a set of n mutually distrusting participants P 1, ..., P n , each with their own private input x i , to compute a function Y = F(x 1, ..., x n ), such that at the end of the protocol, all participants learn the correct value of Y, while secrecy of the private inputs is maintained. Classical results in the unconditionally secure MPC indicate that in the presence of an active adversary, every function can be computed if and only if the number of corrupted participants, t a , is smaller than n/3. Relaxing the requirement of perfect secrecy and utilizing broadcast channels, one can improve this bound to t a < n/2.

All existing MPC protocols assume that uncorrupted participants are truly honest, i.e., they are not even curious in learning other participant secret inputs. Based on this assumption, some MPC protocols are designed in such a way that after elimination of all misbehaving participants, the remaining ones learn all information in the system. This is not consistent with maintaining privacy of the participant inputs. Furthermore, an improvement of the classical results given by Fitzi, Hirt, and Maurer indicates that in addition to t a actively corrupted participants, the adversary may simultaneously corrupt some participants passively. This is in contrast to the assumption that participants who are not corrupted by an active adversary are truly honest.

This paper examines the privacy of MPC protocols, and introduces the notion of an omnipresent adversary, which cannot be eliminated from the protocol. The omnipresent adversary can be either a passive, an active or a mixed one. We assume that up to a minority of participants who are not corrupted by an active adversary can be corrupted passively, with the restriction that at any time, the number of corrupted participants does not exceed a predetermined threshold. We will also show that the existence of a t-resilient protocol for a group of n participants, implies the existence of a t'-private protocol for a group of n¿ participants. That is, the elimination of misbehaving participants from a t-resilient protocol leads to the decomposition of the protocol.

Our adversary model stipulates that a MPC protocol never operates with a set of truly honest participants (which is a more realistic scenario). Therefore, privacy of all participants who properly follow the protocol will be maintained. We present a novel disqualification protocol to avoid a loss of privacy of participants who properly follow the protocol.

Item ID: 8630
Item Type: Conference Item (Research - E1)
ISBN: 978-3-642-00467-4
ISSN: 1611-3349
Keywords: multi-party computation; omnipresent adversary; proactive secret sharing; t-resilient protocols; t-private protocols
Additional Information:

Proceedings published in Lecture Notes in Computer Science, Volume 5443 (ISSN: 1611-3349)

Funders: International Association for Cryptographic research
Date Deposited: 27 Apr 2010 04:27
FoR Codes: 08 INFORMATION AND COMPUTING SCIENCES > 0804 Data Format > 080499 Data Format not elsewhere classified @ 100%
08 INFORMATION AND COMPUTING SCIENCES > 0805 Distributed Computing > 080599 Distributed Computing not elsewhere classified @ 0%
SEO Codes: 89 INFORMATION AND COMMUNICATION SERVICES > 8999 Other Information and Communication Services > 899999 Information and Communication Services not elsewhere classified @ 100%
Downloads: Total: 1006
Last 12 Months: 68
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page