Paper 2020/976

Synchronizable Exchange

Ranjit Kumaresan, Srinivasan Raghuraman, and Adam Sealfon


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).

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
secure multiparty computationfair exchangecompletenesspreprocessing
Contact author(s)
rakumare @ visa com
srraghur @ visa com
asealfon @ berkeley edu
2020-10-07: last of 2 revisions
2020-08-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ranjit Kumaresan and Srinivasan Raghuraman and Adam Sealfon},
      title = {Synchronizable Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2020/976},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.