Secure multi-party computation (MPC) allows a group of participants to compute a function over their private inputs without revealing the inputs themselves. While MPC is a cornerstone of modern cryptography, achieving fairness—the guarantee that if one party receives the output, all parties do—remains a significant challenge, particularly when a majority of participants are malicious.
Presented at TCC 2023, this research introduces a novel building block called Synchronizable Fair Exchange ($\mathcal{F}_{\text{SyX}}$). This primitive demonstrates that 2-party interactions are more powerful than previously assumed, providing a path to $n$-party fairness even in the presence of a dishonest majority.
The Challenge of Fairness
In the "dishonest majority" setting, where more than half of the participants may be corrupt, achieving fairness is notoriously difficult. A seminal result by Fitzi et al. (2005) established that no 2-party primitive is "complete" for achieving guaranteed output delivery (an even stronger property than fairness) in an $n$-party setting.
This paper shifts the focus: if we aim specifically for fairness rather than guaranteed delivery, can we find a simple 2-party building block that is complete for $n$ parties? The answer lies in $\mathcal{F}_{\text{SyX}}$.
Introducing $\mathcal{F}_{\text{SyX}}$
The Synchronizable Fair Exchange is a "reactive" 2-party primitive. Unlike traditional "one-shot" primitives, $\mathcal{F}_{\text{SyX}}$ maintains state and operates in two distinct phases:
- The Load Phase: Two parties submit their private inputs along with a set of predicates (rules). The primitive issues a "receipt" confirming the data is securely loaded.
- The Trigger Phase: At a later time, either party can "trigger" the primitive by providing a witness that satisfies the pre-defined predicates. Once triggered, the primitive releases the output to both parties simultaneously.
Scaling to $n$ Parties via Synchronization
To achieve $n$-party fairness, the authors propose a protocol where every pair of participants is connected by an instance of $\mathcal{F}_{\text{SyX}}$. The synchronization is achieved through the design of the witnesses.
The witness required to trigger one pair's exchange is constructed to include receipts or outputs from other pairs. This creates a "chain reaction": if an adversary triggers one exchange to obtain their share of the output, they inadvertently provide the honest party with the witness needed to trigger all other exchanges. This ensures that either every honest party receives the computation's output or none of them do.
To prevent indefinite stalling by an adversary, the primitive is clock-aware. It tracks protocol "rounds" and enforces timeouts, ensuring the protocol eventually terminates.
Key Insights and Results
- Bypassing Impossibility: By targeting fairness specifically, the authors show that 2-party primitives are indeed sufficient for $n$-party protocols, bypassing the limitations suggested by earlier research on guaranteed delivery.
- Reactivity and Witnesses: The reactive nature of $\mathcal{F}_{\text{SyX}}$ and the use of witnesses as "synchronization gears" are the primary drivers of this result.
- Optimistic Preprocessing: $\mathcal{F}_{\text{SyX}}$ can be pre-loaded before the specific function to be computed is even known. In an "optimistic" scenario where all parties behave honestly, the expensive trigger phase is never invoked, making the protocol as efficient as standard (unfair) MPC.
- Completeness: The authors formally prove that $\mathcal{F}_{\text{SyX}}$ is complete for realizing any $n$-party functionality with fairness in a pairwise-connected network.
Complexity and Efficiency
In the standard model, the complexity of an $\mathcal{F}_{\text{SyX}}$ instance is $O(n^2 \lambda \ell_{out})$, where $\lambda$ is the security parameter and $\ell_{out}$ is the output length. However, when utilizing a Random Oracle (RO) model, the complexity of the load phase drops to $O(\lambda)$, significantly enhancing its practicality for preprocessing. Furthermore, a single pre-loaded instance can be reused across multiple different multi-party protocols.
Future Directions
The current proof relies on clock-awareness to ensure termination. The authors conjecture that this might be a fundamental requirement for 2-party primitives to achieve $n$-party fairness, leaving the formal proof of this necessity for future work. Additionally, while the protocol assumes a broadcast channel, existing techniques can be used to mitigate this requirement. Future research may also explore the behavior of $\mathcal{F}_{\text{SyX}}$ in restricted network topologies beyond fully connected graphs.
Summary updated