Brüggemann, Andreas ; Breuer, Malte ; Klinger, Andreas ; Schneider, Thomas ; Meyer, Ulrike (2022)
Secure Maximum Weight Matching Approximation on General Graphs.
CCS '22: 2022 ACM SIGSAC Conference on Computer and Communications Security. Los Angeles, USA (07.11.2022)
doi: 10.1145/3559613.3563209
Konferenzveröffentlichung, Bibliographie
Kurzbeschreibung (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 block 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. To maximize the scalability of our approach, we compute an 1/2-approximation instead of an exact solution. For N nodes, our protocol requires O(N log N) rounds, O(N^3) communication, and runs in only 12.5 minutes for N=400.
| Typ des Eintrags: | Konferenzveröffentlichung |
|---|---|
| Erschienen: | 2022 |
| Autor(en): | Brüggemann, Andreas ; Breuer, Malte ; Klinger, Andreas ; Schneider, Thomas ; Meyer, Ulrike |
| Art des Eintrags: | Bibliographie |
| Titel: | Secure Maximum Weight Matching Approximation on General Graphs |
| Sprache: | Englisch |
| Publikationsjahr: | 7 November 2022 |
| Ort: | New York, NY |
| Verlag: | ACM |
| Buchtitel: | WPES'22: Proceedings of the 21st Workshop on Privacy in the Electronic Society |
| Veranstaltungstitel: | CCS '22: 2022 ACM SIGSAC Conference on Computer and Communications Security |
| Veranstaltungsort: | Los Angeles, USA |
| Veranstaltungsdatum: | 07.11.2022 |
| DOI: | 10.1145/3559613.3563209 |
| Kurzbeschreibung (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 block 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. To maximize the scalability of our approach, we compute an 1/2-approximation instead of an exact solution. For N nodes, our protocol requires O(N log N) rounds, O(N^3) communication, and runs in only 12.5 minutes for N=400. |
| Zusätzliche Informationen: | 21st Workshop on Privacy in the Electronic Society |
| Fachbereich(e)/-gebiet(e): | DFG-Graduiertenkollegs DFG-Graduiertenkollegs > Graduiertenkolleg 2050 Privacy and Trust for Mobile Users |
| Hinterlegungsdatum: | 15 Nov 2022 14:20 |
| Letzte Änderung: | 24 Jan 2023 13:12 |
| PPN: | 504045555 |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum