TY - GEN
T1 - Efficient Privacy-Preserving Approximation of the Kidney Exchange Problem
AU - Breuer, Malte
AU - Meyer, Ulrike
AU - Wetzel, Susanne
N1 - Publisher Copyright:
© 2024 Copyright held by the owner/author(s).
PY - 2024/7/1
Y1 - 2024/7/1
N2 - 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.
AB - 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.
KW - Kidney Exchange
KW - Privacy
KW - Secure Multi-Party Computation
UR - http://www.scopus.com/inward/record.url?scp=85199279155&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85199279155&partnerID=8YFLogxK
U2 - 10.1145/3634737.3645015
DO - 10.1145/3634737.3645015
M3 - Conference contribution
AN - SCOPUS:85199279155
T3 - ACM AsiaCCS 2024 - Proceedings of the 19th ACM Asia Conference on Computer and Communications Security
SP - 306
EP - 322
BT - ACM AsiaCCS 2024 - Proceedings of the 19th ACM Asia Conference on Computer and Communications Security
T2 - 19th ACM Asia Conference on Computer and Communications Security, AsiaCCS 2024
Y2 - 1 July 2024 through 5 July 2024
ER -