Secure Maximum Weight Matching Approximation on General Graphs (Full Version)

Andreas Brüggemann; Malte Breuer; Andreas Klinger; Thomas Schneider; Ulrike Meyer

Paper 2022/1173

Secure Maximum Weight Matching Approximation on General Graphs (Full Version)

Andreas Brüggemann

, TU Darmstadt

Malte Breuer

, RWTH Aachen University

Andreas Klinger

, RWTH Aachen University

Thomas Schneider

, TU Darmstadt

Ulrike Meyer

, RWTH Aachen University

Abstract

Privacy-preserving protocols for matchings on general graphs can be used for applications such as online dating, bartering, or kidney donor exchange. In addition, they can act as a building blocks for more complex protocols. While privacy preserving protocols for matchings on bipartite graphs are a well-researched topic, the case of general graphs has experienced significantly less attention so far. We address this gap by providing the first privacy-preserving protocol for maximum weight matching on general graphs. We present two protocol variants, which both compute an $1/2-$approximation instead of an optimal solution in favor of scalability. For $N$ nodes, the first variant requires $\mathcal{O}(N \log^2 N)$ rounds and $\mathcal{O}(N^3\log N)$ communication, and the second variant requires only $\mathcal{O}(N \log N)$ rounds and $\mathcal{O}(N^3)$ communication. We implement both variants and find that the first variant runs in $14.9$ minutes for $N=300$ nodes, while the second variant requires only $5.1$ minutes for $N=300$, and $12.5$ minutes for $N=400$.

Note: Full version of a short paper at WPES 2022

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. 2022 Workshop on Privacy in the Electronic Society (WPES '22)
DOI: 10.1145/3559613.3563209
Keywords: Matching General Graphs Secure Multi-Party Computation Approximation
Contact author(s): brueggemann @ encrypto cs tu-darmstadt de
breuer @ itsec rwth-aachen de
klinger @ itsec rwth-aachen de
schneider @ encrypto cs tu-darmstadt de
meyer @ itsec rwth-aachen de
History: 2022-09-20: revised; 2022-09-07: received; See all versions
Short URL: https://ia.cr/2022/1173
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1173,
      author = {Andreas Brüggemann and Malte Breuer and Andreas Klinger and Thomas Schneider and Ulrike Meyer},
      title = {Secure Maximum Weight Matching Approximation on General Graphs (Full Version)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1173},
      year = {2022},
      doi = {10.1145/3559613.3563209},
      url = {https://eprint.iacr.org/2022/1173}
}