Efficient Privacy-Preserving Approximation of the Kidney Exchange Problem

Malte Breuer, Ulrike Meyer, Susanne Wetzel

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

Abstract

The kidney exchange problem (KEP) seeks to find possible exchanges among pairs of patients and their incompatible kidney donors while meeting specific optimization criteria such as maximizing the overall number of possible transplants. Recently, several privacy-preserving protocols for solving the KEP have been proposed. However, the protocols known to date lack scalability in practice since the KEP is an NP-complete problem. We address this issue by proposing a novel privacy-preserving protocol which computes an approximate solution for the KEP that scales well for the large numbers of patient-donor pairs encountered in practice. As opposed to prior work on privacy-preserving kidney exchange, our protocol is generic w.r.t. the security model that can be employed. Compared to the most efficient privacy-preserving protocols for kidney exchange existing to date, our protocol is entirely data oblivious and it exhibits a far superior run time performance. As a second contribution, we use a real-world data set to simulate the application of our protocol as part of a kidney exchange platform, where patient-donor pairs register and de-register over time, and thereby determine its approximation quality in a real-world setting.

Original languageEnglish
Title of host publicationACM AsiaCCS 2024 - Proceedings of the 19th ACM Asia Conference on Computer and Communications Security
Pages306-322
Number of pages17
ISBN (Electronic)9798400704826
DOIs
StatePublished - 1 Jul 2024
Event19th ACM Asia Conference on Computer and Communications Security, AsiaCCS 2024 - Singapore, Singapore
Duration: 1 Jul 20245 Jul 2024

Publication series

NameACM AsiaCCS 2024 - Proceedings of the 19th ACM Asia Conference on Computer and Communications Security

Conference

Conference19th ACM Asia Conference on Computer and Communications Security, AsiaCCS 2024
Country/TerritorySingapore
CitySingapore
Period1/07/245/07/24

Keywords

  • Kidney Exchange
  • Privacy
  • Secure Multi-Party Computation

Fingerprint

Dive into the research topics of 'Efficient Privacy-Preserving Approximation of the Kidney Exchange Problem'. Together they form a unique fingerprint.

Cite this