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 $$-hybrid model, the two parties load $$ with some input, and following this, either party can trigger $$ with a suitable ``witness'' at a later time to receive the output from $$. Crucially the other party also receives output from $$ when $$ is triggered. The trigger witnesses allow us to synchronize the trigger phases of multiple instances of $$, thereby aiding in the design of fair multiparty protocols. Additionally, a pair of parties may reuse a single a priori loaded instance of $$ in any number of multiparty protocols (possibly involving different sets of parties).