Efficient General-Adversary Multi-Party Computation

Secure multi-party computation (MPC) allows a set

$\mathcal{P}$

of

n

players to evaluate a function

f

in presence of an adversary who corrupts a subset of the players. In this paper we consider active, general adversaries, characterized by a so-called adversary structure

$\mathcal{Z}$

which enumerates all possible subsets of corrupted players. In particular for small sets of players general adversaries better capture real-world requirements than classical threshold adversaries.

Protocols for general adversaries are “efficient” in the sense that they require

$|\mathcal{Z}|^{\mathcal{O}(1)}$

bits of communication. However, as

$|\mathcal{Z}|$

is usually very large (even exponential in

n

), the exact exponent is very relevant. In the setting with perfect security, the most efficient protocol known to date communicates

$\mathcal{O}(|\mathcal{Z}|^3$

) bits; we present a protocol for this setting which communicates

$\mathcal{O}(|\mathcal{Z}|^2$

) bits. In the setting with statistical security,

$\mathcal{O}(|\mathcal{Z}|^3$

) bits of communication is needed in general (whereas for a very restricted subclass of adversary structures, a protocol with communication

$\mathcal{O}(|\mathcal{Z}|^2$

) bits is known); we present a protocol for this setting (without limitations) which communicates

$\mathcal{O}(|\mathcal{Z}|^1$

) bits.