Privacy-preserving Kidney Donor Exchange

• Applicants: Professorin Dr.-Ing. Ulrike Meyer; Dr. Anja Mühlfeld
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems ; Epidemiology and Medical Biometry/Statistics ; Nephrology
• Term: from 2020 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 419340256

• Final Report Year: 2025

Final Report Abstract

Kidney exchange enables patients with medically incompatible living donors to still receive a compatible kidney transplant, by finding matches between multiple patient-donor pairs such that these can exchange their donors among each other. The existing kidney exchange systems today face significant security challenges, as they neither prevent manipulation of the exchange computation nor adequately protect the sensitive data of patients and donors. In this project, we devised a new model of a privacy-preserving kidney exchange system that protects against these security issues. Our model follows a decentralized approach in that the computation of exchanges is distributed among a set of computing peers. At discrete points in time the computing peers then execute a secure multi-party computation (SMPC) protocol among each other in order to compute a set of exchanges among the patients’ and donors’ that are registered with the system. This setup guarantees that a computing peer is neither able to learn any information on the input data of the patients and donors nor to manipulate the computation of exchanges. We developed, implemented, and evaluated five different SMPC protocols for kidney exchange, using different algorithmic approaches. All of them are able to cover all desirable functional requirements discussed with medical transplant experts w.r.t. the exchange structures, the matching criteria, and the prioritization criteria supported by them. To evaluate the impact of the run time overhead induced by SMPC and the influence of the different algorithmic approaches on the number of transplants that can be achieved over time, we developed a simulation framework that accounts for the many different parameters that influence the performance of a kidney exchange system (e.g., the interval at which new patients are registered). We used a real-world data set, which we obtained from the United Network for Organ Sharing (UNOS) in the USA, to simulate both the performance of our model of a privacypreserving kidney exchange system as well as the performance of the non-privacy-preserving reference model that mimics the existing centralized kidney exchange systems. Based on these simulations, we were able to show that our approach only induces a small and sometimes even negligible impact on the number of found transplants over time for most parameter combinations that are found in practice. At the same time it provides for significantly stronger security guarantees compared to the existing centralized systems.

Link to the final report

https://doi.org/10.34657/29445

Publications

• A Privacy-Preserving Protocol for the Kidney Exchange Problem. Proceedings of the 19th Workshop on Privacy in the Electronic Society, 151-162. ACM.
  Breuer, Malte; Meyer, Ulrike; Wetzel, Susanne & Mühlfeld, Anja
  
• Introducing a Framework to Enable Anonymous Secure Multi-Party Computation in Practice. 2021 18th International Conference on Privacy, Security and Trust (PST), 1-7. IEEE.
  Breuer, Malte; Meyer, Ulrike & Wetzel, Susanne
  
• Privacy-Preserving Maximum Matching on General Graphs and its Application to Enable Privacy-Preserving Kidney Exchange. Proceedings of the Twelfth ACM Conference on Data and Application Security and Privacy, 53-64. ACM.
  Breuer, Malte; Meyer, Ulrike & Wetzel, Susanne
  
• Secure Maximum Weight Matching Approximation on General Graphs. Proceedings of the 21st Workshop on Privacy in the Electronic Society, 83-87. ACM.
  Brüggemann, Andreas; Breuer, Malte; Klinger, Andreas; Schneider, Thomas & Meyer, Ulrike
  
• Solving the Kidney Exchange Problem Using Privacy-Preserving Integer Programming. 2022 19th Annual International Conference on Privacy, Security & Trust (PST), 1-10. IEEE.
  Breuer, Malte; Hein, Pascal; Pompe, Leonardo; Temme, Ben; Meyer, Ulrike & Wetzel, Susanne
  
• Wenn der eigene Spender nicht passt … Nierentransplantation als Cross-over-Lebendnierenspende. Nieren- und Hochdruckkrankheiten, 51(09), 378-384.
  Breuer, M.; Meyer, U.; Wetzel, S.; Floege, J. & Mühlfeld, A.
  
• Efficient Integration of Exchange Chains in Privacy-Preserving Kidney Exchange. 2024 21st Annual International Conference on Privacy, Security and Trust (PST), 1-10. IEEE.
  Breuer, Malte; Meyer, Ulrike & Wetzel, Susanne
  
• Efficient Privacy-Preserving Approximation of the Kidney Exchange Problem. Proceedings of the 19th ACM Asia Conference on Computer and Communications Security, 306-322. ACM.
  Breuer, Malte; Meyer, Ulrike & Wetzel, Susanne
  
• Prioritization and exchange chains in privacy-preserving kidney exchange. Journal of Computer Security, 32(4), 349-404.
  Breuer, Malte; Hein, Pascal; Pompe, Leonardo; Meyer, Urike & Wetzel, Susanne
  
• Privacy-Preserving Kidney Exchange. PhD thesis, RWTH Aachen University
  M. Breuer