Cryptology ePrint Archive: Report 2020/153

Constructing Secure Multi-Party Computation with Identifiable Abort

Nicholas-Philip Brandt and Sven Maier and Tobias Müller and Jörn Müller-Quade

Abstract: Statistical Multi-Party Computation (MPC) protocols based on two-party Oblivious Transfer (OT) have one severe drawback: the adversary can abort the protocol without repercussions. (Ishai, Ostrovsky, and Zikas, Crypto 14) introduced the notion of Identifiable Abort (IA). We extend the work of (Fitzi, Garay, Maurer, and Ostrovsky, Crypto 01) and investigate, under which conditions n-party MPC can be constructed from smaller functionalities in the setting of IA. Previous work already contains an impossibility result for two-party functionalities (Ishai, Strovski, and Seyalioglu, TCC 12) and a universal n-party setup (Ishai, Ostrovsky, and Zikas, Crypto 14).

We thus investigate setup functionalities of size between 3 and (n-1). In this paper we give novel upper bounds for the sizes of functionalities needed for IA. In particular, we find out, that it is possible to construct n-party MPC with IA from an (n-1)-party setup and a broadcast, if at least 3 parties are honest. We achieve our result by using a new and innovative technique called conflict graph and its complementary association graph, which uses a broadcast channel to model the knowledge of honest parties regarding the identity of malicious parties.

Category / Keywords: foundations / Multi-Party Computation, Simulation-Based Security, Identifiable Abort, Conflict Graph

Date: received 11 Feb 2020

Contact author: nicholas brandt at inf ethz ch, svmaier@ira uni-karlsruhe de

Available format(s): PDF | BibTeX Citation

Version: 20200213:132550 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]