  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.
