Privacy-Preserving Maximum Matching on General Graphs and its Application to Enable Privacy-Preserving Kidney Exchange

Malte Breuer, Ulrike Meyer, Susanne Wetzel

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations

Abstract

To this day, there are still some countries where the exchange of kidneys between multiple incompatible patient-donor pairs is restricted by law. Typically, legal regulations in this context are put in place to prohibit coercion and manipulation in order to prevent a market for organ trade. Yet, in countries where kidney exchange is practiced, existing platforms to facilitate such exchanges generally lack sufficient privacy mechanisms. In this paper, we propose a privacy-preserving protocol for kidney exchange that not only addresses the privacy problem of existing platforms but also is geared to lead the way in overcoming legal issues in those countries where kidney exchange is still not practiced. In our approach, we use the concept of secret sharing to distribute the medical data of patients and donors among a set of computing peers in a privacy-preserving fashion. These computing peers then execute our new Secure Multi-Party Computation (SMPC) protocol among each other to determine an optimal set of kidney exchanges. As part of our new protocol, we devise a privacy-preserving solution to the maximum matching problem on general graphs. We have implemented the protocol in the SMPC benchmarking framework MP-SPDZ and provide a comprehensive performance evaluation. Furthermore, we analyze the practicality of our protocol when used in a dynamic setting where patients and donors arrive and depart over time) based on a data set from the United Network for Organ Sharing.

Original languageEnglish
Title of host publicationCODASPY 2022 - Proceedings of the 12th ACM Conference on Data and Application Security and Privacy
Pages53-64
Number of pages12
ISBN (Electronic)9781450392204
DOIs
StatePublished - 14 Apr 2022
Event12th ACM Conference on Data and Application Security and Privacy, CODASPY 2022 - Virtual, Online, United States
Duration: 24 Apr 202227 Apr 2022

Publication series

NameCODASPY 2022 - Proceedings of the 12th ACM Conference on Data and Application Security and Privacy

Conference

Conference12th ACM Conference on Data and Application Security and Privacy, CODASPY 2022
Country/TerritoryUnited States
CityVirtual, Online
Period24/04/2227/04/22

Keywords

  • kidney exchange
  • matching algorithms
  • privacy
  • secure multi-party computation

Fingerprint

Dive into the research topics of 'Privacy-Preserving Maximum Matching on General Graphs and its Application to Enable Privacy-Preserving Kidney Exchange'. Together they form a unique fingerprint.

Cite this