Solving the Kidney Exchange Problem Using Privacy-Preserving Integer Programming

Abstract

The kidney exchange problem (KEP) seeks to determine a constellation of exchanges that maximizes the number of possible transplants between a set of patients and their incompatible donors. Recently, Secure Multi-Party Computation (SMPC) techniques were used to devise privacy-preserving protocols that allow the solving of the KEP in a distributed fashion. However, these protocols lack sufficient performance in practice. In the non-privacy-preserving case, the most efficient algorithms solving the KEP are based on integer programming. It is in this context, that we propose a privacy-preserving protocol based on these integer programming techniques that efficiently solves the KEP in a privacy-preserving fashion. We prove the security of this protocol and analyze its complexity. Furthermore, we provide a comprehensive performance evaluation of an implementation of the protocol in the SMPC benchmarking framework MP-SPDZ.

Authors 6

1. Malte Breuer Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Aachen,Germany

   RWTH Aachen University, Aachen, Germany

2. Pascal Hein Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Aachen,Germany

   RWTH Aachen University, Aachen, Germany

3. Leonardo Pompe Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Aachen,Germany

   RWTH Aachen University, Aachen, Germany

4. Ben Temme Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Aachen,Germany

   RWTH Aachen University, Aachen, Germany

5. Ulrike Meyer Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University,Aachen,Germany

   RWTH Aachen University, Aachen, Germany

6. Susanne Wetzel

   Stevens Institute of Technology

   Affiliation as printed

   Stevens Institute of Technology,Hoboken,NJ,USA

   Stevens Institute of Technology, Hoboken, NJ, USA