Secure Computation Without Agreement

Shafi Goldwasser, Yehuda Lindell

TL;DR

This paper introduces a relaxed definition of secure multi-party computation that decouples the notion of agreement from security. This allows for the construction of protocols that are secure even when parties can arbitrarily abort, and crucially, these protocols do not rely on broadcast channels, a significant limitation in prior work. This breakthrough enables secure computation in point-to-point networks for any number of corrupted parties, even under composition.

What Problem Does This Paper Address?

Secure multi-party computation (MPC) allows a group of parties to jointly compute a function on their private inputs without revealing anything beyond the desired output. A long-standing challenge in MPC has been achieving security when a significant fraction of parties (one-third or more) are corrupted. This is particularly difficult because many MPC protocols rely on a "broadcast channel" primitive, which itself requires complex protocols like authenticated Byzantine agreement. Recent work showed that authenticated Byzantine agreement is not secure under concurrent or parallel composition when more than one-third of parties are corrupted. This raised serious questions about the composability of MPC protocols in general, especially in settings where many executions might occur. The paper tackles this by questioning the necessity of strict agreement for secure computation and proposing a way to bypass the limitations imposed by Byzantine agreement.

Methods

The core of the paper's contribution lies in a novel definition of secure computation that allows for "abort." This means that some honest parties might abort the computation and output a special symbol, rather than their intended output. This relaxation is key because it decouples the requirement of all parties agreeing on an outcome (or agreeing to abort) from the core security properties of privacy, correctness, and input independence.

The authors then introduce a new primitive called "broadcast with abort." This is a weaker version of the Byzantine Generals problem where parties can either output a value or abort. They show that this primitive can be securely realized in a point-to-point network for any number of corrupted parties using a simple, 2-round deterministic protocol.

This "broadcast with abort" primitive is then used as a compiler to transform existing MPC protocols that rely on broadcast channels into equivalent protocols for point-to-point networks. This transformation is efficient, preserving the round complexity of the original protocols. The paper also introduces techniques to achieve partial fairness, even without a broadcast channel, for a significant range of corrupted parties.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Decoupling Agreement from Security: The most significant insight is that strict agreement (all parties outputting the same thing, or all aborting) is not essential for secure computation. Allowing parties to abort individually, while still preserving privacy and correctness, unlocks new possibilities.
  • "Broadcast with Abort" as a Building Block: This new primitive, while weaker than traditional Byzantine agreement, is surprisingly powerful. It's sufficient to replace broadcast channels in existing MPC protocols, enabling secure computation in point-to-point networks without the composition limitations of authenticated Byzantine agreement.
  • Circumventing Byzantine Agreement Limitations: By avoiding the need for authenticated Byzantine agreement, the paper sidesteps the known composition issues that arise when more than one-third of parties are corrupted. This is a major step towards more robust and composable MPC.
  • Efficiency Gains: The proposed "broadcast with abort" protocol is very efficient (2 rounds), leading to efficient transformations of existing broadcast-based protocols into point-to-point equivalents.

Key Results

  • Secure Computation with Abort: The paper presents protocols for secure multi-party computation with abort (and partial or no fairness) in a point-to-point network for any number of corrupted parties ($t < n$), without requiring a broadcast channel or trusted setup.
  • Efficient Protocol Transformation: A compiler is presented that transforms any broadcast-based MPC protocol into a point-to-point protocol that is secure with abort and no fairness, preserving round complexity.
  • Partial Fairness Achieved: Protocols are presented that achieve partial fairness in a point-to-point network for $t \ge n/2$ (computational setting) and $t < n/2$ (information-theoretic setting), without a broadcast channel.
  • Composability: The work removes the obstacle to achieving secure computation that composes in parallel or concurrently, for any $t < n$, by eliminating the reliance on broadcast channels.

Limitations and Future Work

The paper acknowledges that its efficient transformation (Theorem 1.1) does not preserve fairness. While it achieves secure computation with abort and no fairness, achieving partial fairness requires additional techniques (Theorem 1.2). The authors also note that their work focuses on self-composition and that achieving general universal composability (where a protocol can run concurrently with any other protocols) still requires a common reference string for certain cases. Future work could explore achieving stronger fairness guarantees in the point-to-point model and further investigating universal composability without a common reference string.

Summary updated

BibTeX
@article{goldwasser2002secure,
  author = {Shafi Goldwasser and Yehuda Lindell},
  title = {{Secure Computation Without Agreement}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2002},
}
Figure