Realistic failures in secure multi-party computation

Vassilis Zikas, Sarah Hauser, Ueli Maurer

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In secure multi-party computation, the different ways in which the adversary can control the corrupted players are described by different corruption types. The three most common corruption types are active corruption (the adversary has full control over the corrupted player), passive corruption (the adversary sees what the corrupted player sees) and fail-corruption (the adversary can force the corrupted player to crash irrevocably). Because fail-corruption is inadequate for modeling recoverable failures, the so-called omission corruption was proposed and studied mainly in the context of Byzantine Agreement (BA). It allows the adversary to selectively block messages sent from and to the corrupted player, but without actually seeing the message. In this paper we propose a modular study of omission failures in MPC, by introducing the notions of send-omission (the adversary can selectively block outgoing messages) and receive-omission (the adversary can selectively block incoming messages) corruption. We provide security definitions for protocols tolerating a threshold adversary who can actively, receive-omission, and send-omission corrupt up to t a , t ρ , and t σ players, respectively. We show that the condition 3t a +t ρ +t σ <n is necessary and sufficient for perfectly secure MPC tolerating such an adversary. Along the way we provide perfectly secure protocols for BA under the same bound. As an implication of our results, we show that an adversary who actively corrupts up to t a players and omission corrupts (according to the already existing notion) up to t ω players can be tolerated for perfectly secure MPC if 3t a +2t ω <n. This significantly improves a result by Koo in TCC 2006.

Original languageEnglish
Title of host publicationTheory of Cryptography
Subtitle of host publication6th Theory of Cryptography Conference, TCC 2009, Proceedings
EditorsOmer Reingold
Place of PublicationBerlin, Heidelberg
Number of pages20
ISBN (Electronic)978-3-642-00457-5
ISBN (Print)978-3-642-00456-8
Publication statusPublished - 17 Mar 2009
Event6th Theory of Cryptography Conference - San Francisco, United States
Duration: 15 Mar 200917 Mar 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer, Berlin, Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference6th Theory of Cryptography Conference
Abbreviated titleTCC 2009
CountryUnited States
CitySan Francisco
Internet address

Fingerprint Dive into the research topics of 'Realistic failures in secure multi-party computation'. Together they form a unique fingerprint.

Cite this