Revisiting the Efficiency of Malicious Two-Party Computation

David P. Woodruff

Introduction

In the realm of secure two-party computation (2PC), the goal is for two parties, Alice and Bob, to compute a function $f(x, y)$ over their private inputs without revealing anything beyond the output. While Yao’s garbled circuits provide a robust foundation for "semi-honest" scenarios—where parties follow the protocol but attempt to learn extra information—the malicious model presents a significantly higher hurdle. In this model, a participant might actively deviate from the protocol to cheat or gain an unfair advantage.

This paper introduces Expander-checker, a novel protocol that leverages the structural properties of expander graphs to achieve malicious security with unprecedented efficiency. By optimizing the "cut-and-choose" paradigm, the author reduces the communication and computation overhead required to ensure input consistency, outperforming previous state-of-the-art methods asymptotically.

The Challenge of Input Consistency

The standard approach for achieving security against malicious adversaries is the "cut-and-choose" technique. Alice creates $m$ versions of a garbled circuit; Bob chooses a subset to "open" and verify for correctness, then evaluates the remaining circuits.

A critical bottleneck in this process is input consistency: how can Bob be certain that Alice used the exact same input $x$ for every circuit he evaluates? Previous solutions, such as the "Equality-checker," required Alice to commit to the consistency of every pair of circuits. This led to a communication cost that scales quadratically ($O(m^2)$) with the number of circuits, creating a massive overhead as security requirements (and thus $m$) increased.

The Expander-checker Protocol

The core innovation of this work is replacing the "complete graph" approach of checking every circuit pair with a sparse but highly connected expander graph (specifically Ramanujan graphs).

  • The Expander Trick: In an expander graph, even though each node (representing a circuit) is connected to only a few others, the graph's expansion properties ensure that any large subset of nodes will have many edges connecting to the rest of the graph.
  • Reduced Commitments: Instead of $O(m^2)$ consistency checks, Alice only needs to provide checks for the edges defined by the expander graph. Since these graphs can be $d$-regular (where $d$ is a constant), the number of commitments drops to $O(m)$.
  • Rigorous Security: The paper provides a new graph-theoretic framework to bound the probability of a malicious Alice successfully cheating. Notably, the author identifies and corrects errors in the security analysis of previous protocols, showing that the actual cheating probability for the Equality-checker was less favorable than previously claimed.

Efficiency Comparison

The primary advantage of the Expander-checker is its asymptotic dominance. By effectively removing the $m^2$ penalty associated with input wires ($I$) found in earlier works, it achieves a communication complexity of $O(m \cdot g)$, where $g$ is the number of gates.

Comparison of the Expander-checker protocol against existing schemes across symmetric encryption, exponentiations, and communication costs.

As shown in the table above, for large circuits where the number of inputs is significant, Expander-checker saves a factor of $\ln(1/\epsilon)$ (the statistical security parameter) in both communication and symmetric encryption operations. Furthermore, it maintains the optimal $O(I)$ number of public-key operations (exponentiations), which are typically the most computationally expensive part of the protocol.

Conclusion and Future Work

While the Expander-checker is asymptotically superior, the author acknowledges that the "hidden constants" in the construction of Ramanujan graphs may impact performance for small, practical security parameters. In such specific settings, simpler methods like the Equality-checker might still be competitive.

Future research directions include finding even more practical explicit expander constructions and integrating this expander-based approach with recent simulation-based security proofs to create protocols that are both theoretically optimal and highly efficient in practice.

Summary updated

BibTeX
@inproceedings{woodruff2007revisiting,
  author = {David P. Woodruff},
  title = {{Revisiting the Efficiency of Malicious Two-Party Computation}},
  booktitle = {EUROCRYPT},
  year = {2007},
  doi = {10.1007/978-3-540-72540-4\_5},
}
Figure