Paper 2020/976

Synchronizable Exchange

Ranjit Kumaresan, Srinivasan Raghuraman, and Adam Sealfon

Abstract

Fitzi, Garay, Maurer, and Ostrovsky (Journal of 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 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 fairness in a setting where all $n$ parties are pairwise connected by independent instances of $\mathcal{F}_{\mathsf{SyX}}$. In the $\mathcal{F}_{\mathsf{SyX}}$-hybrid model, the two parties load $\mathcal{F}_{\mathsf{SyX}}$ with some input, and following this, either party can trigger $\mathcal{F}_{\mathsf{SyX}}$ with a suitable ``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 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 reuse a single a priori loaded instance of $\mathcal{F}_{\mathsf{SyX}}$ in any number of multiparty protocols (possibly involving different sets of parties).