Paper 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

We propose an intuitive approach for constructing and analyzing Multi-Party Computation protocols with Identifiable Abort (ID-MPC) based on simple graph-theory. On a high level, in our approach, honest parties publicly announce conflicts with malicious parties via broadcast whenever they catch them misbehaving, thus inducing a Conflict Graph (CG). We directly link the sufficient and necessary conditions for the (identifiable) abort of a protocol to publicly verifiable graph-theoretical properties of the Conflict Graph. To demonstrate its power, we use our technique to reduce the necessary requirements for ID-MPC in the Universal Composability framework with a dishonest majority. State-of-the-art protocols in the dishonest majority setting are posited in the Correlated-Randomness model where one n-party setup provides randomness that is n-wise correlated to all other parties’ randomness. Using our technique we are able to reduce the degree of correlation in the this randomness from $n$ to $n-1$. Additionally, if $n$ is sufficiently small, then our upper bound can be transitively expanded, i.e., for $t \leq n−3$ corruptions among $n$ parties we can construct $n$-party ID-MPC from correlated randomness among each set of $t+2$ parties.

Note: Major changes: - Reformulation of the main results for clearer exposition to better fit with related work - Fixing broken protocols