Synchronizable Exchange

Ranjit Kumaresan, Srinivasan Raghuraman, Adam Sealfon

TL;DR

This paper introduces a new two-party cryptographic building block called Synchronizable Fair Exchange ($\mathcal{F}_{\text{SyX}}$). The authors prove that this primitive is "complete" for achieving fairness in $n$-party secure computation, meaning any complex multiparty protocol can be made fair just by using independent instances of this simple 2-party tool, even when a majority of participants are dishonest.

What Problem Does This Paper Address?

In the world of Secure Multiparty Computation (MPC), we want a group of people to compute a function over their private inputs without revealing anything but the result. However, a major hurdle is fairness: ensuring that either everyone gets the output or no one does.

If a majority of the participants are malicious (the "dishonest majority" setting), achieving fairness is notoriously difficult. Standard protocols often allow an adversary to see the output and then "abort," preventing honest parties from receiving it. A landmark 2005 paper by Fitzi et al. showed that no simple 2-party primitive is "complete" for achieving Guaranteed Output Delivery (a stronger version of fairness where honest parties always get the result).

This paper asks a more targeted question: Is there a 2-party primitive that is complete for fairness alone? If so, can we design it such that multiple instances can be "synced" together to handle complex multiparty scenarios?

Methods

The authors propose the Synchronizable Fair Exchange ($\mathcal{F}_{\text{SyX}}$) primitive. It operates in two distinct phases:

  1. The Load Phase: Two parties "load" the primitive with private inputs and public functions/predicates. Upon successful loading, the primitive issues a "receipt."
  2. The Trigger Phase: At any later time, either party can "trigger" the primitive by providing a "witness" (a piece of data that satisfies a specific condition). If the witness is valid, the primitive computes the output and delivers it to both parties simultaneously.

The "Sync" Innovation: The genius of $\mathcal{F}_{\text{SyX}}$ lies in the trigger condition. By requiring the trigger witness to include receipts from other instances of $\mathcal{F}_{\text{SyX}}$, the authors can "link" multiple 2-party exchanges together. This ensures that if one pair of parties triggers their exchange, it provides the necessary "proof" for other parties to trigger theirs, creating a domino effect that ensures everyone gets the output.

The protocol also utilizes clock-awareness. The primitive knows what "round" it is, allowing it to set timeouts. This prevents a malicious party from waiting until the very last second to trigger an instance, leaving honest parties with no time to react.

Datasets

As a theoretical cryptography paper, this work does not use empirical datasets or training benchmarks. It relies on mathematical proofs and formal security models (like the Universal Composability framework).

Key Insights and Ideas

  • Bypassing Impossibility: While Fitzi et al. proved you can't get Guaranteed Output Delivery from 2-party primitives, this paper shows that Fairness is achievable. This clarifies the boundary of what simple building blocks can and cannot do.
  • Synchronization via Witnesses: Instead of needing a complex "global" fair primitive, we can use many "local" 2-party primitives that are aware of each other through shared witnesses.
  • Preprocessing and Reuse: A single loaded instance of $\mathcal{F}_{\text{SyX}}$ can be reused across many different multiparty protocols. This makes the "expensive" part of the protocol (the load phase) a one-time setup cost.
  • Reduction to Fair Reconstruction: The authors show that you don't need to run the entire computation through $\mathcal{F}_{\text{SyX}}$. Instead, you can run a standard (unfair) MPC to get secret shares of the result, and then use $\mathcal{F}_{\text{SyX}}$ only for the final "fair reconstruction" of those shares.

Key Results

  • Completeness Theorem: The paper formally proves that $\mathcal{F}_{\text{SyX}}$ is complete for realizing any $n$-party functionality with fairness in the presence of a dishonest majority.
  • Efficiency: The complexity of each $\mathcal{F}_{\text{SyX}}$ instance is $O(n^2 \lambda \ell_{out})$, where $n$ is the number of parties and $\lambda$ is the security parameter. Crucially, this is independent of the complexity of the function being computed.
  • Preprocessing Model: The authors provide a version of the protocol that works in a "preprocessing" setting, where parties can set up their $\mathcal{F}_{\text{SyX}}$ instances before they even know what function they want to compute.

Limitations and Future Work

  • Theoretical Nature: This is a foundational theory paper. While it proves existence and completeness, a high-performance implementation would likely require specific hardware (like Intel SGX) or a blockchain to act as the "bulletin board" for receipts, as mentioned in the authors' follow-up discussions.
  • Clock Synchronization: The protocol assumes a synchronous network where parties have a shared notion of "rounds." In highly asynchronous environments (like the open internet), the timing-based triggers would be much harder to manage.
  • Communication Overhead: While the complexity is independent of the function, the $O(n^2)$ scaling with the number of parties means that for very large groups, the number of required 2-party instances could become a bottleneck.

Summary updated

BibTeX
@article{kumaresan2020synchronizable,
  author = {Ranjit Kumaresan and Srinivasan Raghuraman and Adam Sealfon},
  title = {{Synchronizable Exchange}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2020},
  url = {https://openreview.net/forum?id=KCBSsFfERDi},
}
Figure