  Background: The kidney exchange problem (KEP) addresses the matching of
patients in need for a replacement organ with compatible living donors. Ideally
many medical institutions should participate in a matching program to increase
the chance for successful matches. However, to fulfill legal requirements
current systems use complicated policy-based data protection mechanisms that
effectively exclude smaller medical facilities to participate. Employing secure
multi-party computation (MPC) techniques provides a technical way to satisfy
data protection requirements for highly sensitive personal health information
while simultaneously reducing the regulatory burdens.
  Results: We have designed, implemented, and benchmarked SPIKE, a secure
MPC-based privacy-preserving KEP which computes a solution by finding matching
donor-recipient pairs in a graph structure. SPIKE matches 40 pairs in cycles of
length 2 in less than 4 minutes and outperforms the previous state-of-the-art
protocol by a factor of 400x in runtime while providing medically more robust
solutions.
  Conclusions: We show how to solve the KEP in a robust and privacy-preserving
manner achieving practical performance. The usage of MPC techniques fulfills
many data protection requirements on a technical level, allowing smaller health
care providers to directly participate in a kidney exchange with reduced legal
processes.
