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

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

Available format(s)
Publication info
Published elsewhere. 2022 Workshop on Privacy in the Electronic Society (WPES '22)
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
2022-09-20: revised
2022-09-07: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.