Efficient Integration of Exchange Chains in Privacy-Preserving Kidney Exchange

Traditionally, kidney exchange allows patients with an incompatible living kidney donor to exchange their donors in form of exchange cycles. Today, additional transplants are achieved through so-called exchange chains. These are initiated by an altruistic donor, who donates a kidney without requiring anything in return. In practice, kidney exchange is typically facilitated through central platforms, which compute potential exchange cycles and chains for a large number of patients and donors. To overcome the severe security issues of this centralized approach, several secure multi-party computation (SMPC) protocols for kidney exchange have been proposed recently. However, the privacy-preserving protocols proposed to date either do not scale for a sufficient number of patients and donors or do not support exchange chains. In this paper, we present the first SMPC protocol that both supports exchange chains and yields efficient run times for a large number of patients and donors. We have implemented our protocol in the framework MP-SPDZ and evaluated its run time performance. Besides, we present evaluation results based on real-world data for the use of our protocol in a dynamic setting, where patient-donor pairs and altruistic donors arrive and depart over time.