Synchronizable Exchange

Ranjit Kumaresan, Srinivasan Raghuraman, Adam Sealfon

Introduction

In Secure Multiparty Computation (MPC), a group of participants aims to compute a function over their private inputs such that only the result is revealed. A critical challenge in this field is fairness: ensuring that either all parties receive the output or none do. In settings where a majority of participants may be dishonest, achieving fairness is notoriously difficult.

Historically, research has shown a divide between what is possible with simple building blocks and complex protocols. A landmark study by Fitzi et al. (2005) demonstrated that no simple 2-party primitive is "complete" for achieving Guaranteed Output Delivery (a strong form of fairness where honest parties are guaranteed the result regardless of adversarial behavior). This paper investigates a more specific question: Is there a 2-party primitive that is complete for fairness alone? The authors introduce Synchronizable Fair Exchange ($\mathcal{F}_{\text{SyX}}$), proving it to be a sufficient and complete building block for fair $n$-party computation.

The Synchronizable Fair Exchange Primitive

The core contribution of this work is the $\mathcal{F}_{\text{SyX}}$ primitive, a two-party cryptographic tool designed to be "linked" across multiple instances. The primitive operates in two distinct phases:

  1. The Load Phase: Two parties initialize the primitive with their private inputs and specific public predicates. Once successfully loaded, the primitive issues a "receipt" to both parties, serving as a cryptographic proof of initialization.
  2. The Trigger Phase: At a later time, either party can activate the primitive by providing a "witness"—a data string that satisfies the pre-defined condition. If the witness is valid, the primitive computes the output and delivers it to both parties simultaneously.

The Innovation of Synchronization

The "Synchronizable" aspect of $\mathcal{F}_{\text{SyX}}$ allows multiple 2-party exchanges to be chained together. By requiring the trigger witness of one instance to include receipts from other $\mathcal{F}_{\text{SyX}}$ instances, the authors create a dependency chain. This ensures a "domino effect": if one pair of parties triggers their exchange, it reveals the necessary information for other pairs to trigger theirs, maintaining fairness across the entire network.

Furthermore, the primitive is clock-aware. By incorporating a shared notion of time (rounds), the primitive can enforce timeouts. This prevents a common adversarial tactic where a malicious party waits until the final moment to trigger an exchange, leaving honest parties with no time to respond or propagate the result.

Achieving Multi-party Fairness

The paper demonstrates that $\mathcal{F}_{\text{SyX}}$ can be used to achieve fairness in any $n$-party functionality. Rather than running an entire complex computation through the primitive, the authors propose a more efficient reduction to Fair Reconstruction.

In this model, parties first use a standard, unfair MPC protocol to compute secret shares of the final result. They then use $\mathcal{F}_{\text{SyX}}$ instances only for the final step: exchanging these shares fairly. Because the primitive is synchronizable, the reconstruction of shares happens in a coordinated manner, ensuring that no party can learn the final result without others also having the means to do so.

Key Results and Efficiency

The research provides several foundational results for the cryptographic community:

  • Completeness Theorem: The authors formally prove that $\mathcal{F}_{\text{SyX}}$ is complete for realizing any $n$-party functionality with fairness, even when a majority of parties are dishonest. This clarifies the theoretical boundary of what 2-party primitives can achieve.
  • Efficiency: The complexity of an $\mathcal{F}_{\text{SyX}}$ instance is $O(n^2 \lambda \ell_{out})$, where $n$ is the number of parties, $\lambda$ is the security parameter, and $\ell_{out}$ is the output length. Notably, the complexity of the fair exchange is independent of the complexity of the function being computed.
  • Preprocessing Model: The protocol supports a preprocessing phase. Parties can "load" their $\mathcal{F}_{\text{SyX}}$ instances before the specific function to be computed is even known, allowing the most computationally expensive parts of the protocol to be handled as a one-time setup cost.

Limitations and Future Outlook

While $\mathcal{F}_{\text{SyX}}$ provides a robust theoretical framework, its practical application faces certain hurdles. The protocol assumes a synchronous network; in highly asynchronous environments like the open internet, managing timing-based triggers becomes significantly more complex. Additionally, while the complexity is independent of the function, the $O(n^2)$ scaling relative to the number of participants suggests that communication overhead could become a bottleneck for very large-scale computations.

Future work may involve implementing $\mathcal{F}_{\text{SyX}}$ using specialized hardware (such as Trusted Execution Environments) or leveraging blockchain technology to serve as a persistent bulletin board for receipts and witnesses, potentially easing the synchronization requirements in real-world deployments.

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