International Association
for Cryptologic Research

Fitzi, Garay, Maurer, and Ostrovsky (J.\ Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with {\em guaranteed output delivery}. In this work, we introduce a new $2$-party primitive $\mathcal{F}_{\mathsf{SyX}}$ (``synchronizable fair exchange'') and show that it is complete for realizing any $n$-party functionality with {\em fairness} in a setting where all parties are pairwise connected by instances of $\mathcal{F}_{\mathsf{SyX}}$. In the $\mathcal{F}_{\mathsf{SyX}}$-hybrid model, the two parties {\em load} $\mathcal{F}_{\mathsf{SyX}}$ with some input, and following this, either party can {\em trigger} $\mathcal{F}_{\mathsf{SyX}}$ with a ``witness'' at a later time to receive the output from $\mathcal{F}_{\mathsf{SyX}}$. Crucially the other party also receives output from $\mathcal{F}_{\mathsf{SyX}}$ when $\mathcal{F}_{\mathsf{SyX}}$ is triggered. The trigger witnesses allow us to {\em synchronize} the trigger phases of multiple instances of $\mathcal{F}_{\mathsf{SyX}}$, thereby aiding in the design of fair multiparty protocols. Additionally, a pair of parties may {\em reuse} a single {\em a priori} loaded instance of $\mathcal{F}_{\mathsf{SyX}}$ in any number of multiparty protocols (involving different sets of parties).