Prioritization and exchange chains in privacy-preserving kidney exchange

Abstract

The Kidney Exchange Problem (KEP) aims at finding an optimal set of exchanges among pairs of patients and their medically incompatible living kidney donors as well as altruistic donors who are not associated with any particular patient but want to donate a kidney to any person in need. Existing platforms that offer the finding of such exchanges for patient-donor pairs and altruistic donors are organized in a centralized fashion and operated by a single platform operator. This makes them susceptible to manipulation and corruption. Recent research has targeted these security issues by proposing decentralized Secure Multi-Party Computation (SMPC) protocols for solving the KEP. However, these protocols fail to meet two important requirements for kidney exchange in practice. First, they do not allow for altruistic donors. While such donors are not legally allowed in all countries, they have been shown to have a positive effect on the number of transplants that can be found. Second, the existing SMPC protocols do not support prioritization, which is used in existing platforms to give priority to certain exchanges or patient-donor pairs, e.g., to patients who are hard to match due to their medical characteristics. In this paper, we introduce a generic gate for implementing prioritization in kidney exchange. We extend two existing SMPC protocols for solving the KEP such that they allow for altruistic donors and prioritization and present one novel SMPC protocol for solving the KEP with altruistic donors and prioritization based on dynamic programming. We prove the security of all protocols and analyze their complexity. We implement all protocols and evaluate their performance for the setting where altruistic donors are legally allowed and for the setting where they are not. Thereby, we determine the performance impact of the inclusion of altruistic donors and obtain those approaches that perform best for each setting.

Keywords

Kidney Exchange Privacy Secure Multi-Party Computation

1. Introduction

In recent years, kidney disease has risen to the 10th most common cause of death worldwide accounting for about 1.3 million deaths in 2019 [39]. The preferred treatment for kidney disease is transplantation [7]. However, the waiting lists for a kidney transplant from a deceased person are long in most countries (e.g., the waiting list of Eurotransplant contained more than 10 000 patients at the end of 2021 [25]). An alternative to donation through such a waiting list is living kidney donation where a patient finds a friend or relative who is willing to donate one of her kidneys. Even if a patient finds such a person, the donor organ might still not be medically compatible with the patient. Kidney exchange aims at solving this problem by considering multiple such patients and their associated incompatible donors (in the following referred to as patient-donor pairs) and finding constellations such that these can exchange their kidney donors among each other.

The most common form of such exchanges are exchange cycles where the kidney donors are exchanged in a cyclic fashion such that the donor of a pair is compatible with the patient of the succeeding pair in the cycle and thus each patient in the cycle is matched with a compatible donor. In such a cycle it is then guaranteed that the donor of a patient-donor pair only donates her kidney if the corresponding patient of the pair also receives a kidney transplant in return.

In addition to exchange cycles, also so-called exchange chains are possible. These are initiated by an altruistic donor who is not associated with any particular patient and who is willing to donate one of her kidneys without requiring any form of compensation. A chain then continues the same way as an exchange cycle with the exception that the donor of the last pair in the chain either donates to the waiting list or functions as an altruistic donor at a later point in time (also referred to as bridge donor). Since altruistic donations are not legal in many countries, many kidney exchange platforms only consider exchange cycles [10].

Given a set of patient-donor pairs (and altruistic donors), the Kidney Exchange Problem (KEP) is then defined as finding a constellation of exchange cycles (and chains) that is optimal w.r.t. some set of pre-defined criteria [1]. Commonly, the most important criterion is to maximize the number of patients that are matched with a compatible donor [7,10]. Additionally, most countries use some form of prioritization criteria to break ties among multiple maximal solutions or to give preference to certain patient-donor pairs (e.g., pairs containing patients who already wait for a kidney donation for a long time or who are particularly difficult to match) [7,10].

In practice, kidney exchange is realized by central (nationwide) platforms where the hospitals register their respective patient-donor pairs [7,10]. The platform operator then periodically solves the KEP for all patient-donor pairs that are registered at a given point in time. Afterwards, the hospitals are informed about the computed exchanges for their respective patient-donor pairs.

From a security perspective, this centralized approach is highly problematic since the medical data of all patient-donor pairs and altruistic donors is present in plaintext at the central platform. This is particularly severe since it potentially violates the crucial requirement for kidney exchange that all patient-donor pairs are to be treated equally. For example, an attacker who learns the medical data of all patient-donor pairs that are registered with the platform can use this knowledge to adapt the data of a particular patient-donor pair such that it better fits the available donors and patients. Thereby, the attacker can increase the prioritization score for that particular pair, which gives the pair an advantage over other patient-donor pairs. Note that such an attack is difficult to detect since the prioritization score is often computed based on medical data that is unlikely to be collected again after the match computation. Furthermore, the consequences of any accidental or forced data breach are very severe due to the highly sensitive nature of the concerned data. In the context of kidney exchange, such a data breach may also decrease the trust in the platform and thus influence the willingness of potential donors to register with the platform.

Recent research [8,14,16,17] aims to solve these problems by proposing decentralized solutions based on Secure Multi-Party Computation (SMPC). These approaches follow the client-server model [13], i.e., the patient-donor pairs (clients) distribute their private medical data among a set of computing peers (servers), who execute an SMPC protocol among each other to solve the KEP in a distributed fashion. The use of SMPC ensures that the computing peers neither learn the private medical data of the patient-donor pairs nor the computed exchanges, thus mitigating the consequences of data breaches and protecting the privacy of the patient-donor pairs. Additionally, these approaches provide for impartiality in that they ensure that all patient-donor pairs are treated equally. However, the existing approaches still come along with certain disadvantages. In particular, the protocol from [16] only allows for the detection of exchange cycles of size two, i.e., cycles involving only two patient-donor pairs, whereas most existing platforms consider cycles up to size three. The protocol $π_{KEP - RND}$ [17] allows for cycles of any maximum cycle size but it follows a very inefficient brute force approach. While the protocol $π_{KEP - IP}$ [14] achieves much more efficient run times, it is not entirely data oblivious (i.e., the protocol flow is not independent of the input). The protocol from [8] only computes an approximation to the KEP and it is also not entirely data-oblivious.

Comparing these recent theoretical results with the requirements for kidney exchange in practice, there is still a gap in research. In particular, the existing protocols only allow for the detection of exchange cycles whereas in practice there are also countries where exchange chains are allowed [7,10]. Furthermore, most platforms for kidney exchange in practice use some way of prioritization whereas the existing SMPC protocols (except for the approximation protocol from [8]) only allow for the maximization of the overall number of transplants.

Contributions. The goal of this paper is to further close this gap between the requirements of kidney exchange in practice and the properties provided by privacy-preserving solutions to the KEP. The focus lies on privacy-preserving solutions to the KEP that allow for altruistic donors and for prioritization. In particular, this paper comprises the following six main contributions:

We devise a privacy-preserving gate for prioritization. This gate allows for the computation of a prioritization score between the donor of one patient-donor pair (or an altruistic donor) and the patient of another pair. Since the existing platforms consider a wide range of different prioritization criteria, we first categorize the existing criteria according to their implementation in a privacy-preserving setting. Then, we present a generic gate for prioritization that covers all the previously categorized criteria.

We extend the existing SMPC protocol $π_{KEP - RND}$ [17], which computes an exact solution to the KEP for any maximum cycle size using a brute force approach, such that it includes the possibility for prioritization. Furthermore, we present a variant of the protocol that also allows for altruistic donors and the detection of exchange chains. Since the protocol was originally designed for the fully distributed setting, we adapt it to the client-server model, where the patient-donor pairs (clients) provide their input to a set of computing peers (servers) who execute an SMPC protocol among each other to solve the KEP.

We extend the existing SMPC protocol $π_{KEP - IP}$ [14], which computes an exact solution to the KEP for any maximum cycle size based on an integer programming approach, such that it includes the possibility for prioritization. As for the protocol $π_{KEP - RND}$ , we also present a variant that allows for altruistic donors and the detection of exchange chains.

We present one entirely novel SMPC protocol $π_{KEP - DP}$ for solving the KEP with prioritization and exchange chains based on dynamic programming. Our novel protocol $π_{KEP - DP}$ constitutes a middle ground between the two existing protocols in that it is not as efficient as the protocol $π_{KEP - IP}$ but has the advantage of being entirely data oblivious.1

¹
Note that it is hard to develop an efficient data oblivious SMPC protocol for the KEP since the KEP is NP-complete for cycle size restrictions larger than 2 [1].

We prove the security of all protocols in the semi-honest security model considering an honest majority, i.e., we assume that there is an adversary who is able to corrupt less than half of the computing peers and all corrupted computing peers strictly follow the protocol specification but try to learn as much as possible on the input of the parties that are not corrupted.

We implement all three protocols with prioritization and exchange chains in the SMPC benchmarking framework MP-SPDZ [28] and provide an extensive performance evaluation determining the impact of the inclusion of prioritization and exchange chains on their performance. Note that we achieve considerably faster run times for the protocols $π_{KEP - RND}$ and $π_{KEP - IP}$ compared to the results reported in [17] and [14], respectively. For the protocol $π_{KEP - RND}$ , we attribute this to the replacement of homomorphic encryption in the fully distributed setting by replicated secret sharing [4] in the client-server model. For the protocol $π_{KEP - IP}$ , we applied the same changes as proposed in the extended version [15] of [14], i.e., we use a higher degree of parallelization in MP-SPDZ, we update the MP-SPDZ version from 0.2.5 to 0.3.5, and we replace Shamir’s secret sharing [36] by the replicated secret sharing scheme from [4].

Our evaluations show that the most efficient approach both in terms of run time and network traffic is the protocol $π_{KEP - IP}$ based on integer programming. For the KEP with prioritization and exchange cycles only, the protocol still finishes within 7 minutes for 20 patient-donor pairs and within 1.5 hours for up to 35 pairs. Note that such run times are acceptable for the use case of kidney exchange since existing platforms typically only require to solve the KEP once per day or even only once every couple of months [7,10]. With respect to the inclusion of prioritization and exchange chains, our evaluations show that prioritization only has a small impact on the run time of the protocols $π_{KEP - RND}$ and $π_{KEP - DP}$ whereas it has a considerable impact on the run time of the protocol $π_{KEP - IP}$ . The inclusion of exchange chains only has a small impact on the run time of the protocols $π_{KEP - IP}$ and $π_{KEP - DP}$ if the maximum chain length is three. However, the run time performance of all three protocols decreases considerably with the inclusion of exchange chains of length greater than three (cf. Section 6.4).

Outline. The remainder of this paper is structured as follows. In Section 2, we introduce the relevant background on SMPC and the algorithmic approaches on which our protocols are based. In Section 3, we present cryptographic building blocks that are used as subroutines in our protocols. In Section 4, we devise a novel gate for prioritization in kidney exchange. In Section 5, we present the three protocols for solving the KEP and explain how they can be extended to altruistic donors. In Section 6, we provide the evaluation of the protocols and in Section 7, we present existing research that is related to our work. In Section 8, we draw a conclusion of our work and identify potential directions for future research.

2. Preliminaries

In this section, we provide the formal background on which our privacy-preserving protocols for solving the Kidney Exchange Problem (KEP) are based.

2.1. Graph theory

A directed graph is a graph $G = (V, E, ω)$ where the edge $(i, j) \in E$ is directed from node i to node j and ω is a function that assigns a weight $ω (e)$ to each edge in E. Such a graph is typically represented by an adjacency matrix A of size $| V | \times | V |$ where $A (i, j) = 1$ if $(i, j) \in E$ and $M (i, j) = 0$ , otherwise, and a weight matrix W of size $| V | \times | V |$ where $W (i, j) = ω (i, j)$ . Given a matrix M, we denote the i-th row by $M (i, -)$ , the j-th column by $M (-, j)$ , and the submatrix with entries $M (i, j)$ where $i_{1} ⩽ i ⩽ i_{2}$ and $j_{1} ⩽ j ⩽ j_{2}$ by $M ([i_{1} : i_{2}], [j_{1} : j_{2}])$ .

2.2. Secure multi-party computation

SMPC allows a set of parties $K = {K_{1}, \dots, K_{| K |}}$ to compute a functionality $F : {({0, 1}^{*})}^{| K |} \to {({0, 1}^{*})}^{| K |}$ in a distributed fashion such that each party only learns its private input and output and what can be deduced from both. In this paper, we consider a client-server setup [13], where a set of input peers (clients) delegates the computation to a set of computing peers (servers). The input peers only provide the input to the functionality $F$ and receive their private output whereas the computing peers execute the SMPC protocol that implements $F$ .

Security definition. When defining security in the context of SMPC it is common to consider the ideal world vs. real world paradigm [27]. In the ideal world setting, all parties send their inputs to a trusted external party. This trusted party then computes the functionality $F$ and provides each party with its corresponding output. In the real world setting, the parties need to compute $F$ in a distributed setting without relying on a trusted external party. The goal of SMPC is to achieve the same level of security in the real-world setting as in the ideal world setting. Intuitively, an SMPC protocol is said to be secure if an adversary who controls a set of corrupted parties $I_{C} : = {K_{i_{1}}, \dots, K_{i_{| I_{C} |}}}$ cannot infer more information from the execution of the protocol in the real world than he could in the ideal world setting.

More formally, we assume the following setup based on the standard definitions for SMPC from [18,27]. We assume that the parties are connected in a peer-to-peer fashion by reliable communication channels, i.e., the authenticity of the data sent over these channels is guaranteed. We consider the semi-honest model where the adversary controls a set of corrupted parties $I_{C} \subset K$ who strictly follow the protocol specification but gather all information they obtain during the protocol execution. The adversary then tries to use the information obtained by the corrupted parties to derive any information on the inputs and outputs of the other, non-corrupted parties. Finally, we assume an honest majority among the parties. This means that the adversary is only able to corrupt a minority of the parties, i.e., $| I_{C} | < \frac{| K |}{2}$ .

Definition 1 (Security in the Semi-Honest Model, based on [27]).

Let $\overline{x} = (x_{1}, \dots, x_{| K |})$ and let $F : {({0, 1}^{*})}^{| K |} \to {({0, 1}^{*})}^{| K |}$ be a multi-party functionality, where $x_{i}$ denotes the input of party $K_{i}$ and $F_{i} (\overline{x})$ denotes the output of party $K_{i}$ . For $I_{C} = {K_{i_{1}}, \dots, K_{i_{| I_{C} |}}} \subset K$ , let ${\overline{x}}_{I_{C}} = (x_{i_{1}}, \dots, x_{i_{| I_{C} |}})$ and $F_{I_{C}} (\overline{x}) = (F_{i_{1}} (\overline{x}), \dots, F_{i_{| I_{C} |}} (\overline{x}))$ . Let π be a $| K |$ -party protocol that implements functionality $F$ and let ${VIEW}_{i}^{π} = (x_{i}, r_{i}, m_{i, 1}, \dots, m_{i, l}, s)$ be the view of $K_{i}$ during the execution of π on $\overline{x}$ with statistical security parameter $s \in N$ , where $r_{i}$ are the internal coin tosses of $K_{i}$ and $m_{i, j}$ is the j-th message received by $K_{i}$ during the execution of π. We say that π securely implements $F$ if there exists a probabilistic polynomial-time algorithm $S$ such that for every $I_{C} \subset K$ with $| I_{C} | < \frac{| K |}{2}$ it holds that $\begin{matrix} {(S (1^{s}, I_{C}, {\overline{x}}_{I_{C}}, F_{I_{C}} (\overline{x})), F (\overline{x}))}_{\overline{x}, s} and {({VIEW}_{I_{C}}^{π} (\overline{x}, s), {OUTPUT}^{π} (\overline{x}, s))}_{\overline{x}, s} \end{matrix}$ are statistically indistinguishable, where ${VIEW}_{I_{C}}^{π} (\overline{x}, s) = ({VIEW}_{i_{1}}^{π}, \dots, {VIEW}_{i_{| I_{C} |}}^{π})$ and ${OUTPUT}^{π} (\overline{x}, s)$ denotes the output sequence of all parties during the execution represented by ${VIEW}^{π} (\overline{x})$ .

Intuitively, Definition 1 states that a protocol π is secure if a simulator $S$ can generate the view of a party $K_{i}$ solely based on the party’s input and output such that it is indistinguishable from the real view of the party $K_{i}$ during an execution of π. To prove the security of a protocol π, we thus have to show that such a view can be generated by the simulator $S$ . We denote a simulated value x by $⟨ x ⟩$ .

In order to prove the security of a protocol π that calls a finite set of gates $ρ_{i}$ ( $i \in N$ ) that have already been proven secure in the semi-honest model, the simulator $S_{π}$ of protocol π can simply call the simulator $S_{ρ_{i}}$ for each gate $ρ_{i}$ on the corresponding input and output to that gate. By stating that $S_{π}$ calls the simulator $S_{ρ_{i}}$ , we refer to $S_{π}$ executing the steps that are specified for $S_{ρ_{i}}$ on the corresponding input and output. Thus, in our security proofs it is sufficient to simulate the input and output for a gate $ρ_{i}$ and call the corresponding gate simulator $S_{ρ_{i}}$ .

Underlying secret-sharing scheme. As underlying technique for our SMPC protocols we require a $(t, n)$ linear secret-sharing scheme over $Z_{M}$ where M is either a large prime p or $2^{k}$ for a large integer k. The threshold t in such a scheme indicates that at least t shares are required to reconstruct a shared value. In order to keep our protocols independent from any particular secret-sharing scheme, we use an arithmetic black box (ABB) [21]. This ABB allows for the sharing of values, their reconstruction, and it enables the computing peers to execute linear combinations and multiplications on secret values. Whereas linear combinations of secret values can be executed locally by the computing peers, the multiplication of two secret values requires communication between the computing peers. We denote a secret value x by $[x]$ and we write $[z] \leftarrow [x] \cdot [y]$ for the multiplication of two secret values $[x]$ and $[y]$ . Furthermore, we denote a vector V of secret values by $[V]$ , and a matrix A of secret values by $[A]$ . With $[V] (i)$ (resp. $[A] (i, j)$ ) we denote a single element of a secret vector $[V]$ (resp. matrix $[A]$ ). A negative value $- x$ is defined as $M - x \in Z_{M}$ .

Complexity metrics. We use the two common complexity metrics communication and round complexity. The communication complexity is determined by the overall amount of data that is sent during a protocol execution. The round complexity corresponds to the number of sequential communication steps required by a protocol. Note that steps that can be executed in parallel are counted as a single round.

Setup for privacy-preserving kidney exchange. As common for privacy-preserving kidney exchange [8,14,16], the input peers correspond to the patient-donor pairs or altruistic donors who seek to find exchange partners. They send their private input data to the computing peers using secret sharing. The computing peers execute an SMPC protocol for solving the KEP and provide the patient-donor pairs and altruistic donors with their computed exchange partners. The computing peers can be hosted by large transplant centers, universities, or governmental institutions.

The client-server setup with security in the semi-honest model is commonly considered appropriate for kidney exchange [8,14,16,17] since the computing peers are hosted by institutions that are generally trusted to correctly follow the protocol specification but the collection of a huge amount of sensitive data at a central entity is to be avoided. This level of security significantly mitigates the consequences of a data breach at a computing peer since the shares that are present at a single peer do not reveal any information on the underlying data. Without such knowledge it is also not possible for an attacker to adapt the medical data of a particular patient-donor pair such that the patient is more likely to be matched. Furthermore, the semi-honest security model allows for a much more efficient computation of the exchanges compared to the stronger malicious security model, where the corrupted computing peers may arbitrarily deviate from the protocol specification. Thus, it forms a reasonable trade-off between privacy and performance. Finally, protocols that are secure in the semi-honest model can often be a first step towards protocols that provide for malicious security.

2.3. Kidney exchange terminology

In kidney exchange, a set of patient-donor pairs $P_{i}$ with $i \in P$ aim to find constellations such that they can exchange their kidney donors among each other. Each patient-donor pair $P_{i}$ consists of a patient who seeks for a kidney transplant and her medically incompatible donor who offers a kidney donation. Kidney exchange is then typically modeled using a graph-based approach [7,10]. In particular, the compatibility between the patient-donor pairs is modeled by the so-called compatibility graph $G^{C}$ .

Definition 2 (Compatibility Graph $G^{C}$ ).

For a set of patient-donor pairs $P_{i}$ ( $i \in P$ ), the compatibility graph $G^{C}$ is defined as the directed graph $G^{C} = (V, E, ω)$ which contains one node for each pair $P_{i}$ (i.e., $V = P$ ). For all edges $(i, j) \in E$ , it holds that the donor of pair $P_{i}$ is medically compatible with the patient of pair $P_{j}$ for $i \neq j$ . The weight $ω (i, j)$ of an edge $(i, j)$ is used to prioritize certain edges according to different medical or logistical criteria that differ for individual kidney exchange platforms.

One possibility for finding exchanges between the patient-donor pairs is then to search for so-called exchange cycles in the compatibility graph $G^{C}$ .

Definition 3 (Exchange Cycle).

For a set of patient-donor pairs $P_{i}$ ( $i \in P$ ), an exchange cycle of size λ is a tuple $(P_{i_{1}}, \dots, P_{i_{λ}})$ with $i_{j} \neq i_{k}$ for $j \neq k$ such that the donor of pair $P_{i_{j}}$ is medically compatible with the patient of pair $P_{i_{j + 1}}$ for $j \in {1, \dots, λ - 1}$ and the donor of pair $P_{i_{λ}}$ is medically compatible with the patient of pair $P_{i_{1}}$ .

Exchanges in such a cyclic fashion ensure that the donor of a pair only donates her offered kidney iff the corresponding patient of the pair also receives a compatible kidney transplant in return. In practice, all transplants involved in an exchange cycle have to be executed simultaneously to ensure that a donor cannot retreat after the corresponding patient already received a kidney transplant. Since every single operation on both the donors and the patients requires a considerable amount of medical staff and resources, the maximum size of an exchange cycle is typically restricted to $λ = 2$ or $λ = 3$ [7,9]. A set of exchange cycles is called disjoint and simultaneously executable if they have no patient-donor pair in common. The weight of a cycle is then determined as the sum of the weights of its edges.

In addition to cycles, some platforms also consider so-called exchange chains which are initiated by an altruistic donor $P_{i}^{A}$ ( $i \in A$ ) who offers a kidney donation without requiring any compensation in return.

Definition 4 (Exchange Chain).

For a set of patient-donor pairs $P_{i}$ ( $i \in P$ ) and a set of altruists $P_{i}^{A}$ ( $i \in A$ ), an exchange chain of size κ is a tuple $(P_{i_{1}}^{A}, P_{i_{2}}, \dots, P_{i_{κ}})$ with $i_{j} \neq i_{k}$ for $j \neq k$ such that the altruistic donor $P_{i_{1}}^{A}$ is medically compatible with the patient of pair $P_{i_{2}}$ and the donor of pair $P_{i_{j}}$ is medically compatible with the patient of pair $P_{i_{j + 1}}$ for $j \in {2, \dots, κ - 1}$ .

As for exchange cycles, the weight of an exchange chain is defined as the sum of the weights of its edges. While all transplants in an exchange cycle have to be executed simultaneously, this is not necessarily the case for exchange chains. If the operations in an exchange chain are executed in order, starting at the beginning of a chain, then it is always true that the patient of pair $P_{i}$ receives a transplant before the corresponding donor of pair $P_{i}$ donates her kidney. Thus, in theory it is not necessary to specify an upper bound on the chain length for exchange chains. However, many countries still consider an upper bound κ on the size of exchange chains since long chains increase the probability that the chain breaks due to a donor backing out or a patient’s physical condition becoming worse before receiving a transplant [7,10]. As altruistic kidney donations are illegal in many countries [9], we specify our protocols once for exchange cycles only and then describe how they can be extended such that also exchange chains can be considered.

The goal in kidney exchange is then to find a constellation of exchange cycles (and chains) such that the overall sum of weights of the edges in the constellation is maximized. This problem is commonly referred to as the Kidney Exchange Problem (KEP).

Definition 5 (Kidney Exchange Problem (with Exchange Chains)).

The kidney exchange problem is to find a constellation of disjoint exchange cycles (and chains) of maximum weight for a set of patient-donor pairs $P_{i}$ with $i \in P$ (and a set of altruists $P_{j}^{A}$ with $j \in A$ ).

2.4. Integer programming for kidney exchange

The most common methodology for solving the KEP for exchange cycles and chains of bounded length in the non-privacy-preserving setting is Integer Programming [7,10]. An Integer Program (IP) is a formalism to describe an optimization problem. Let $c \in R^{n}$ , $a_{i} \in R^{n}$ , and $b_{i} \in R$ for $i \in {1, \dots, m}$ . The corresponding IP is then defined as $\begin{matrix} (1) & max {c^{⊤} x | A x = b; x ⩾ 0; x integral} \end{matrix}$ where $x \mapsto c^{⊤} x$ is the objective function, A is the constraint matrix, and b is the bound vector. This form of an IP where only equality constraints occur is called the standard form. Inequalities $a_{i}^{⊤} x ⩽ b_{i}$ can be represented in standard form as $a_{i}^{⊤} x + s_{i} = b_{i}$ where $s_{i} ⩾ 0$ is called a slack variable.

In our protocols, we represent an IP in form of a tableau with objective value $- z = c^{⊤} x$ (the sign is inverted as we maximize the objective function whereas the tableau method is designed for minimization).

Cycle formulation. The most efficient known IP formulation for the KEP is the cycle formulation where a constraint is introduced for each possible cycle of length at most λ (and each possible chain of length at most κ) [1].

Definition 6 (Cycle Formulation).

Let $C$ be the set of all cycles of length at most λ (and chains of length at most κ) in the compatibility graph $G = (V, E)$ . Then, the cycle formulation is defined as $\begin{matrix} (3) & \begin{aligned} maximize & \sum_{C \in C} w_{C} \cdot x_{C} \\ s.t. & \sum_{\begin{array}{c} C \in C \\ v \in V (C) \end{array}} x_{C} ⩽ 1 & for all v \in V \\ x_{C} \in {0, 1} & for all C \in C \end{aligned} \end{matrix}$ where $w_{C}$ is the weight of the cycle or chain $C \in C$ and $x_{C} \in {0, 1}$ for $C \in C$ such that $x_{C} = 1$ iff cycle/chain C is chosen and $x_{C} = 0$ , otherwise.

Subset formulation. In the privacy-preserving setting, we have to keep secret which cycles (and chains) actually exist in the compatibility graph. Therefore, we have to consider the set $C$ of all potential cycles (and chains) in the complete directed graph $G_{K} = (V, E^{'})$ with $V = P$ and $(u, v) \in E^{'}$ for all $u, v \in V$ . For the complete graph $G_{K}$ , this set $C$ is very large, i.e., there are $\sum_{i = 2}^{λ} \frac{| P |!}{(| P | - i)! \cdot i}$ cycles and $\sum_{i = 2}^{κ} \frac{| P |!}{(| P | - i)!}$ chains. However, there are only $\sum_{i = 2}^{max {λ, κ}} \frac{| P |!}{(| P | - i)! \cdot i!}$ different subsets of the nodes in V. Since we are only interested in the cycle (or chain) with the maximum weight for each subset of nodes, we can first determine this cycle (or chain) for each subset and then only use one variable $x_{S}$ for each subset S instead of one variable for each cycle (and chain) in $C$ . Thus, we have to consider significantly less variables at the initial cost of determining the cycle (or chain) of maximum weight for each subset.2

²
This is only more efficient in the privacy-preserving case as only there the complete graph $G_{K}$ has to be considered.

Definition 7 (Subset Formulation, based on [14]).

Let $S$ contain all sets of nodes of size i with $2 ⩽ i ⩽ max {λ, κ}$ and let $μ : S \to C \cup {\emptyset}$ be a mapping that assigns the cycle (or chain) $μ (S)$ with maximum weight of all cycles (and chains) with $V (C) = S$ to each subset $S \in S$ . If there is no such cycle (or chain), let $μ (S) = \emptyset$ . Then, the subset formulation is defined as $\begin{matrix} (4) & \begin{aligned} maximize & \sum_{S \in S} w_{μ (S)} \cdot x_{S} \\ s.t. & \sum_{\begin{array}{c} S \in S \\ v \in S \end{array}} x_{S} ⩽ 1 & for all v \in V \\ x_{S} \in {0, 1} & for all S \in S \end{aligned} \end{matrix}$ where $w_{μ (S)}$ is the weight of the chosen cycle (or chain) $μ (S)$ for the subset $S \in S$ and the variable $x_{S} \in {0, 1}$ indicates for each $S \in S$ whether the corresponding cycle (or chain) $μ (S)$ consisting of the vertices in S is chosen.

We assume that the set $S = {S_{1}, \dots, S_{| S |}}$ is a fixed enumeration of the subsets and that the set $C_{i} = {C_{i, 1}, \dots, C_{i, λ_{i}}, C_{i, λ_{i} + 1}, \dots, C_{i, λ_{i} + κ_{i}}}$ ( $1 ⩽ i ⩽ | S |$ ) is a fixed enumeration of the cycles and chains consisting of the nodes in $S_{i}$ , where $λ_{i}$ is the number of cycles and $κ_{i}$ the number of chains in the subset $S_{i}$ .

Fig. 1.

Example of the relation between the compatibility graph and the corresponding IP and initial tableau for the subset formulation of the KEP. To increase readability, we consider the setting where only exchange cycles are allowed.

Figure 1 shows an example of a compatibility graph for three patient-donor pairs and the corresponding IP and initial tableau for the subset formulation of the KEP.

3. Building blocks

In this section, we introduce gate functionalities and their implementations which we use as subroutines in the three privacy-preserving protocols for solving the KEP detailed in Section 5.

3.1. Basic operations

For the secure comparison of two shared values $[x]$ and $[y]$ we write $[x] \overset{?}{>} [y]$ . A gate for this primitive with statistical security can be realized with linear communication and constant round complexity [19].

Conditional selection is defined as choosing between two values based on a secret bit $[b]$ , i.e., we choose $[x]$ if b is equal to 1 and $[y]$ , otherwise. This corresponds to computing $[b] \cdot ([x] - [y]) + [y]$ and we denote this by $[b] ? [x] : [y]$ .

Sometimes we require to access or update an entry $[V] ([i])$ of a vector where the index $[i]$ is a secret value and where n is the maximum value of i. Such a secret index is first translated into a vector $[I]$ containing the value $[1]$ at position i and $[0]$ at all other positions. This requires $O (n \cdot s)$ communication and $O (log log n)$ rounds [30]. Based on this index vector, the entry $[V] ([i])$ can then be accessed by computing the inner product of $[V]$ and $[I]$ and updated by $[V] (j) \leftarrow [I] (j) ? [x] : [V] (j)$ for $j \in {1, \dots, | V |}$ . Both operations require $| V |$ multiplications that can be executed in parallel. Thus, accessing or updating an entry $[V] ([i])$ overall has communication complexity $O (n \cdot | V | \cdot s)$ and round complexity $O (log log n)$ .

Furthermore, we require a gate $ρ_{SEL - MIN}$ for selecting the index of the first element in a vector V that is equal to 1. We use the implementation from [14] with communication complexity $O (| V | \cdot s)$ and round complexity $O (1)$ .

We also use a gate $ρ_{{DEMUX}^{n}}$ for de-multiplexing a secret value $[x]$ into a binary vector of size n that contains $[1]$ in the x-th entry and $[0]$ , otherwise. Such a gate can be implemented following the approach from [30] with communication complexity $O (n \cdot s)$ and round complexity $O (log log n)$ .

Finally, we require a gate for obliviously shuffling the entries of a vector $[V]$ . Zahur et al. [41] show how such a gate can be implemented using a Waksman network [38]. The resulting gate $ρ_{SHUFFLE}$ has communication complexity $O (| V |^{2} log | V | \cdot s)$ and round complexity $O (log | V |)$ .3

³
We use this implementation as it is part of MP-SPDZ [28], which we use for the implementation of our protocols. We note that there are more efficient shuffling gates for three computing peers that require $O (| V |^{2} \cdot s)$ communication and $O (1)$ rounds [5].

A gate

ρ_{REVERSE - SHUFFLE}

that reverts the shuffling with a permutation σ can be implemented analogously using the permutation

σ^{- 1}

. To initialize the shuffling gate with a random permutation σ, we use a gate

ρ_{GEN - PERM}

which just locally generates a random permutation σ and then shares it among the computing peers.

3.2. Compatibility check for kidney exchange

We use the gate $ρ_{COMP - CHECK}$ from [17] to determine the medical compatibility between a patient in need of a donor organ and a potential donor and thus to determine the existence of an edge in the compatibility graph (cf. Definition 2). Since the gate was originally proposed for homomorphic encryption, we have to apply several changes to it for the setting with secret sharing using computing peers and input peers. The gate from [17] considers the two criteria blood type compatibility and HLA compatibility which are exactly those criteria that are commonly considered necessary for compatibility in kidney exchange [7].

Blood type compatibility. Every human has one of four different blood types (i.e., O, A, B, AB) which indicate whether or not the antigens A or B are present. For blood type compatibility, it is required that the antigens of the donor are also present for the patient. This ensures that the patient has not developed antibodies against the antigens of the donor. For example, if the donor has blood type A, the blood type of the patient has to be either A or AB. The gate $ρ_{COMP - CHECK}$ uses a binary indicator vector $B_{i}^{d}$ to encode the blood type of the donor of patient-donor pair $P_{i}$ . In particular, $B_{i}^{d} (0)$ indicates whether or not the donor of pair $P_{i}$ has blood antigen A and $B_{i}^{d} (1)$ indicates whether or not the donor of pair $P_{i}$ has blood antigen B. In the same way, we encode the blood type of the patient of pair $P_{i}$ by $B_{i}^{p}$ . A donor of a pair $P_{i}$ is then ABO-compatible with a patient of another pair $P_{j}$ iff $\prod_{k \in {0, 1}} 1 - B_{i}^{d} (k) \cdot (1 - B_{j}^{p} (k)) = 1$ .

HLA compatibility. Every human being has leukocyte antigens (HLA) which are inherited from their parents. For each location on the corresponding chromosome, either one or two such antigens are present. A kidney donor is considered as HLA compatible with a patient if and only if the patient has no antibodies against any HLA of the donor. If this is not the case, then it is likely that the immune system of the patient tries to reject the organ. In our gate $ρ_{COMP - CHECK}$ , the HLA of the donor are encoded as a binary indicator vector $A_{i}^{d}$ such that $A_{i}^{d} (j) = 1$ indicates that the donor has HLA j. Similarly, the antibodies of a patient are encoded as a binary indicator vector $A_{i}^{p}$ such that $A_{i}^{p} (j) = 1$ indicates that the patient has an antibody against HLA j. This encoding has two advantages. First, it does not leak the number of a patient’s antibodies, which would reveal information on how difficult the patient is to match. Second, we can determine the HLA compatibility between a donor and a patient by computing the dot product of $A_{i}^{d}$ and $A_{j}^{p}$ . If the dot product equals zero, we know that the patient does not have an antibody against any of the HLA of the donor.

The ideal functionality that computes the compatibility between a patient and a donor based on blood type and HLA compatibility is then defined as follows.

Functionality 1 ( $G_{COMP - CHECK}$ – Compatibility Check for Kidney Exchange, based on [17]).

Let all computing peers hold shares of the blood type indicator vector $[B_{i}^{d}]$ and the antigen indicator vector $[A_{i}^{d}]$ of the donor of patient-donor pair $P_{i}$ as well as the blood type indicator vector $[B_{j}^{p}]$ and the antibody indicator vector $[A_{j}^{p}]$ of the patient of patient-donor pair $P_{j}$ . Then, functionality $G_{COMP - CHECK}$ is given as $\begin{matrix} [o] \leftarrow G_{COMP - CHECK} ([B_{i}^{d}], [A_{i}^{d}], [B_{j}^{p}], [A_{j}^{p}]) \end{matrix}$ where $[o]$ is an encrypted bit indicating whether the donor of patient-donor pair $P_{i}$ and the patient of patient-donor pair $P_{j}$ are medically compatible w.r.t. their blood types and HLAs.

Gate 1

$ρ_{COMP - CHECK}$ , based on [17]

Gate 1 implements functionality $G_{COMP - CHECK}$ (cf. Definition 1). To check for blood type compatibility, we compute for both A and B blood antigens whether they are always present for the patient if they are present for the donor. This corresponds to computing $[1] - [B_{i}^{d}] (k) \cdot ([1] - [B_{j}^{p}] (k))$ for $k \in {0, 1}$ . Note that the term $[B_{i}^{d}] (k) \cdot ([1] - [B_{j}^{p}] (k))$ is always equal to $[0]$ except for the case that $[B_{i}^{d}] (k) = [1]$ and $[B_{j}^{p}] (k) = [0]$ , i.e., for the case that the donor has an antigen that is not present for the patient. For HLA compatibility, we compute the dot product of the donor antigen indicator vector $A_{i}^{d}$ and the patient antibody indicator vector $A_{j}^{p}$ . The dot product is smaller than 1 (i.e., equal to 0) iff for all $k \in {1, \dots, | A_{i}^{d} |}$ it holds that if $A_{i}^{d} (k) = 1$ , then $A_{j}^{p} (k) = 0$ . Thus, the dot product is less than 1 iff the patient has no antibodies against any HLA of the donor, i.e., if donor and patient are HLA compatible. Finally, we have $o = 1$ iff both blood type compatibility and HLA compatibility are given, and $o = 0$ , otherwise.

The correctness of gate $ρ_{COMP - CHECK}$ follows directly from the construction of the blood type and HLA indicator vectors and the correctness of the called gates.

Theorem 8.

Gate $ρ_{COMP - CHECK}$ (cf. Gate 1 ) securely computes functionality $G_{COMP - CHECK}$ (cf. Functionality 1 ).

The proof of Theorem 8 can be found in Appendix C.1.

Complexity analysis. The most expensive operation in the gate $ρ_{COMP - CHECK}$ is the computation of the dot product for HLA compatibility leading to communication complexity $O (| A^{d} |) \cdot s$ and round complexity $O (1)$ , where $| A^{d} |$ indicates the overall number of possible antigens.

Inclusion of altruistic donors. Altruistic donors do not have to be considered explicitly for this gate. We can just model an altruistic donor as a patient-donor pair where all medical input data of the “patient” is set to $[0]$ . This guarantees that the compatibility check also evaluates to $[0]$ for a donor of a pair $P_{i}$ and the “patient” of an altruistic donor $P_{j}^{A}$ .

3.3. Setup of the integer program for the subset formulation

The two protocols $π_{KEP - IP}$ (cf. Section 5.2) and $π_{KEP - DP}$ (cf. Section 5.3) both solve the KEP based on the subset formulation (cf. Definition 7). Thus, they both require a gate $ρ_{IP - SETUP}$ that constructs the initial tableau for the subset formulation based on the input of the patient-donor pairs. Such a gate was already presented in [14] for the KEP without prioritization. In this section, we present an adaptation of the existing gate from [14] that also allows for prioritization, i.e., weighted edges in the compatibility graph. The corresponding ideal functionality $G_{IP - SETUP}$ is given in Functionality 2.

Functionality 2 ( $G_{IP - SETUP}$ – Privacy-Preserving IP Setup for the Subset Formulation).

Let all computing peers hold their respective shares of the secret adjacency matrix $[A]$ and the secret prioritization matrix $[W]$ that encode the compatibility graph $G^{C}$ as well as the public set of subsets $S$ for the subset formulation. Then, functionality $G_{IP - SETUP}$ is given as $\begin{matrix} [T], [M] \leftarrow G_{IP - SETUP} ([A], [W], S) \end{matrix}$ where $[T]$ encodes the initial tableau for the subset formulation with subsets $S$ , and $[M]$ maps each subset $S_{i} \in S$ to one exchange cycle $C_{i, j}$ such that for all $v \in C_{i, j}$ it also holds that $v \in S_{i}$ , for all $(u, v) \in C_{i, j}$ it holds that $A (u, v) = 1$ , and for all other cycles $C_{i, j^{'}}$ it either holds that $w_{C_{i, j^{'}}} < w_{C_{i, j}}$ or $w_{C_{i, j^{'}}} = w_{C_{i, j}}$ and $j^{'} > j$ .

Gate 2

$ρ_{IP - SETUP}$ , based on [14]

Gate $ρ_{IP - SETUP}$ (Gate 2) implements functionality $G_{IP - SETUP}$ (cf. Functionality 2). In a first step, the initial tableau $[T]$ is computed based on the subsets $S$ and the number of patient-donor pairs $| P |$ . Then, we set the first row of the tableau (i.e., the objective coefficients $| S_{i} |$ for $S_{i} \in S$ ) based on the adjacency matrix $[A]$ and the prioritization matrix $[W]$ which encode the compatibility graph. In particular, we determine for each cycle $C_{i, j}$ ( $i \in {1, \dots, | S |}$ , $j \in {1, \dots, λ_{max}}$ ) whether it exists in the compatibility graph. To this end, we verify that all edges $(v, w)$ of the cycle $C_{i, j}$ are present in the matrix $[A]$ . We multiply the thus obtained value by the weight of the cycle (which corresponds to the sum of the edge weights). Then, we compute the secret index $[j_{max}]$ of the cycle that has maximum weight $[h_{max}^{'}]$ of all cycles that consist of the nodes in $S_{i}$ . Finally, we set the values of the i-th row of the mapping $[M]$ to $[1]$ for this index and to $[0]$ , otherwise. The objective value $[T] (1, i)$ is set to the maximum weight $[h_{max}^{'}]$ .

In order to show the correctness of gate $ρ_{IP - SETUP}$ , we have to show that the gate chooses the first cycle of maximum weight for each subset in $S$ . After the first inner for loop, $[H] (i, j)$ encodes the weight of the j-th cycle consisting of the nodes from the i-th subset. In the second for loop, the values $[j_{max}]$ and $[h_{max}^{'}]$ are only updated if the weight of the j-th cycle is strictly larger than the previously maximum weight. Thus, after the for loop it holds that $[j_{max}]$ encodes the index of the first cycle with largest weight and $[h_{max}^{'}]$ encodes the corresponding weight.

Theorem 9.

Gate $ρ_{IP - SETUP}$ (cf. Gate 2 ) securely computes functionality $G_{IP - SETUP}$ (cf. Functionality 2 ).

The proof of Theorem 9 can be found in Appendix C.2.

Complexity analysis. The outer loop of the gate $ρ_{IP - SETUP}$ can be executed in parallel. This leads to communication complexity $O (| S | \cdot λ_{max} \cdot s)$ and round complexity $O (λ_{max})$ for the gate $ρ_{IP - SETUP}$ .

Extension for exchange chains. In Section 5.2.4 and Section 5.3.4, we describe how our protocols $π_{KEP - IP}$ and $π_{KEP - DP}$ can be extended such that they solve the subset formulation of the KEP not only for exchange cycles but for exchange cycles and exchange chains. Therefore, we also have to extend the gate $ρ_{IP - SETUP}$ such that it constructs the initial tableau T and the mapping $M$ for exchange cycles and chains. To determine those input peers that are altruistic donors, the gate receives the secret vector $[A]$ as additional input. An entry $[A] (i) = [1]$ denotes that input peer $P_{i}$ is an altruistic donor whereas $[A] (i) = [0]$ indicates that $P_{i}$ is a regular patient-donor pair.

The main change that comes along with the inclusion of exchange chains is that there are more possible exchange structures for a single subset $S_{i} \in S$ . In particular, we do not only have to consider all possible cycles $C_{i, j}$ that exist for $S_{i}$ but also all chains. Analogous to the number $λ_{i}$ of cycles per subset, we denote the number of exchange chains for a subset $S_{i}$ by $κ_{i}$ . We then add a second loop over all possible chains of a subset after the loop over all cycles. For each chain $C_{i j}$ , we execute the following computations:

Thus, for $j \in 1, \dots, λ_{i}$ the entry $[H] (i, j)$ still encodes the weight of the cycle $C_{i j}$ if it is executable and $[0]$ , otherwise. For $j \in {λ_{i} + 1, \dots, λ_{i} + κ_{i}}$ the entry $[H] (i, j)$ encodes the weight of the chain $C_{i j}$ if it is executable and $[0]$ , otherwise. The remainder of the gate stays the same as for cycles only. For completeness, we provide the detailed specification of the adapted gate $ρ_{IP - SETUP - CC}$ in Appendix B (Gate 4).

The inclusion of exchange chains increases the communication complexity to $O ((λ_{max} + κ_{max}) \cdot | S | \cdot s)$ and the round complexity to $O (λ_{max} + κ_{max})$ where $κ_{max} = κ!$ for maximum chain size κ.

4. Prioritization for kidney exchange

While the main objective of a kidney exchange platform is typically to maximize the overall number of compatible patient-donor pairs that are found, most platforms use a prioritization function at least to break ties if there are multiple optimal solutions. The criteria that are considered for such prioritization and also the influence of the different criteria vary considerably across different platforms and countries [7,10]. In this section, we present our novel gate $ρ_{PRIO}$ that computes the weight of the edge in the compatibility graph $G^{C}$ between the donor of a patient-donor pair $P_{i}$ and the patient of a pair $P_{j}$ . This weight can then be used to prioritize certain patient-donor pairs or exchanges over others.

4.1. Prioritization criteria

Table 1
Categories of prioritization criteria, their corresponding edge weights, and examples for each category

Category Weight for the edge $(i, j)$ Example criteria

Number of compatible patient-donor pairs $w_{base}$ – maximize the number of found compatible pairs

Pre-score ${ps}_{j}$ for the patient of pair $P_{j}$ – waiting time

– highly sensitized patient

Equality criteria $w_{eq}^{k}$ if $D OT -P RODUCT ({EQ}_{i}^{k}, {EQ}_{j}^{k}) < (>, =) b_{eq}^{k}$ for two binary vectors ${EQ}_{i}^{k}$ and ${EQ}_{j}^{k}$ – same blood type

– HLA-matching score

Difference criteria $w_{dif}^{k}$ if $| {dif}_{i}^{k} - {dif}_{j}^{k} | < (>, =) b_{dif}^{k}$ – age difference

– body weight difference

Travel distance $F^{dist} ({hp}_{i}, {hp}_{j})$ for hospital ids ${hp}_{i}$ and ${hp}_{j}$ – minimize the travel distance

Category	Weight for the edge $(i, j)$	Example criteria
Number of compatible patient-donor pairs	$w_{base}$	– maximize the number of found compatible pairs
Pre-score	${ps}_{j}$ for the patient of pair $P_{j}$	– waiting time
– highly sensitized patient
Equality criteria	$w_{eq}^{k}$ if $D OT -P RODUCT ({EQ}_{i}^{k}, {EQ}_{j}^{k}) < (>, =) b_{eq}^{k}$ for two binary vectors ${EQ}_{i}^{k}$ and ${EQ}_{j}^{k}$	– same blood type
– HLA-matching score
Difference criteria	$w_{dif}^{k}$ if $\| {dif}_{i}^{k} - {dif}_{j}^{k} \| < (>, =) b_{dif}^{k}$	– age difference
– body weight difference
Travel distance	$F^{dist} ({hp}_{i}, {hp}_{j})$ for hospital ids ${hp}_{i}$ and ${hp}_{j}$	– minimize the travel distance

We provide an extensive list of criteria that are considered across different platforms and countries and assign them to categories according to the way in which they can be implemented using SMPC. Table 1 provides an overview of the different categories of prioritization criteria.

Number of compatible pairs. The natural criterion that is considered to be most important by most platforms is to maximize the overall number of patients for which a compatible donor is found [7,10]. This is also the only objective that is considered by the existing SMPC protocols for solving the KEP [14,16,17]. If one considers an unweighted compatibility graph, then solving the KEP automatically maximizes the number of found transplants. However, when introducing weights, we have to ensure that a small number of edges of high weight can never lead to the exclusion of a larger number of edges of smaller weight. This can be achieved by adding a large enough publicly known base weight $w_{base}$ to each edge in the graph.

Pre-score. The criteria in this category only depend on a patient-donor pair itself and not on its relation to the other pairs. In particular, for each criterion k and the patient of each patient-donor pair $P_{j}$ , a pre-score ${ps}_{j}^{k}$ is specified. The pre-scores for all criteria k can then be added up to a single pre-computed score ${ps}_{j}$ that is part of the private input of the patient-donor pair $P_{j}$ . The score ${ps}_{j}$ is added to the weight of each edge $(i, j)$ ( $i \in P ∖ {j}$ ). Note that only the pre-score of the patient of the receiving pair $P_{j}$ is relevant since the edge $(i, j)$ concerns the relation between the donor of pair $P_{i}$ and the patient of pair $P_{j}$ .

The actual criteria of this type vary considerably across the different existing kidney exchange platforms. Examples are: Waiting time, time on dialysis, pediatric patients, patients or donors with rare blood types, or so-called highly sensitized patients which are particularly difficult to match [3,7]. Also scores that capture the probability of long-term graft survival such as the Estimated Post Transplant Survival (EPTS) score used by the OPTN fall into this category of criteria [34].

Equality criteria. The third category of criteria prioritizes patients and donors who have at least/at most/exactly some pre-defined bound $b_{eq}^{k}$ of properties relevant for the criterion k in common. In contrast to the pre-score, these criteria depend on the relationship between a particular patient and a particular donor. Thus, they have to be computed at the beginning of each protocol based on the private input of the patient-donor pairs. We model these criteria as follows.

Each criterion k consists of different properties $l_{k}$ and we have a binary indicator vector ${EQ}_{i}^{k}$ for the donor and the patient of each patient-donor pair $P_{i}$ where an entry ${EQ}_{i}^{k} (l_{k})$ indicates whether or not the donor or patient of pair $P_{i}$ has the property $l_{k}$ . We determine the number of properties that the donor of pair $P_{i}$ and the patient of pair $P_{j}$ have in common by computing the dot product of the two vectors ${EQ}_{i}^{k}$ and ${EQ}_{j}^{k}$ . This dot product is then compared to the bound $b_{eq}^{k}$ . If the number of common properties is below/above/equal to the specified bound, a weight $w_{eq}^{k}$ is added to the edge $(i, j)$ .

Criteria that fall into this category include but are not limited to: Prioritization of pairs from the same region, prioritization of transplants where donor and patient have the same blood type, or HLA-matching scores [3,7]. The latter is a very common criterion that measures the number of HLA that a patient and the potential donor have in common.

Difference criteria. The fourth group of criteria prioritizes patients and donors for which the difference between two input values is smaller/larger/equal to some pre-defined bound $b_{dif}^{k}$ for a criterion k. We model these criteria as follows.

For each criterion k, each donor and each patient has an input value ${dif}_{i}^{k}$ . We compute the difference ${dif}_{i}^{k} - {dif}_{j}^{k}$ for the donor of pair $P_{i}$ and the patient of pair $P_{j}$ and check whether it is smaller/larger/equal to the corresponding bound $b_{dif}^{k}$ . If this is the case, we add a pre-defined weight $w_{dif}^{k}$ to the edge $(i, j)$ .

An example for such a criterion that is used in many countries (e.g., Belgium, Poland, Spain, UK) is to prioritize transplants where donor and patient have an age difference smaller than a certain threshold value (e.g., smaller than 20 years) [3]. A similar criterion is the prioritization of transplants where the two donors of an exchange between two patient-donor pairs are of similar age [3]. There are also studies that suggest that the difference in the weight of patient and donor impacts the graft survival rate [33].

Travel distance. Some countries such as Spain [10] aim at minimizing the travel distance between hospital of the donor and hospital of the patient for logistic reasons. A gate that minimizes the travel distance between donor and patient can be implemented efficiently by specifying a public matrix $F^{dist}$ that stores the distance (or a preference value for the distance) between each pair of hospitals that participate in the kidney exchange platform. Determining the edge weight for the travel distance between a patient and a donor can then be achieved by obliviously accessing the corresponding entry of $F^{dist}$ .

4.2. Ideal functionality and gate specification

Since the criteria that are considered by the different platforms vary considerably, we present the prioritization gate and the ideal functionality in a generic and abstract fashion. In particular, we state how each category of criteria can be implemented. Depending on which criteria are then actually considered, one can add the appropriate number of iterations for each category.

Functionality 3 ( $G_{PRIO}$ – Privacy-Preserving Prioritization for the KEP).

Let all computing peers hold their respective shares of the input quotes $[Q_{i}]$ , $[Q_{j}]$ for two patient-donor pairs $P_{i}$ and $P_{j}$ . These contain the secret pre-score $[{ps}_{j}]$ , the binary indicator vectors $[{EQ}_{i}^{k}]$ , $[{EQ}_{j}^{k}]$ ( $k \in {1, \dots, n_{eq}}$ ) for the equality criteria, the secret values $[{dif}_{i}^{k}]$ , $[{dif}_{j}^{k}]$ ( $k \in {1, \dots, n_{dif}}$ ) for the difference criteria, and the identifier of the hospitals $[{hp}_{i}]$ , $[{hp}_{j}]$ for the donor of pair $P_{i}$ and the patient of pair $P_{j}$ . Furthermore, let each computing peer hold the public matrix $F^{dist}$ of weights for the travel distances between the participating hospitals, the public base weight $w_{base}$ for the maximization of the number of transplants, the public weights $w_{eq}^{k}$ and $w_{dif}^{k}$ for each considered equality or difference criterion k, and their respective bounds $b_{eq}^{k}$ and $b_{dif}^{k}$ . Then, functionality $G_{PRIO}$ is given as $\begin{matrix} [w] \leftarrow G_{PRIO} ([Q_{i}], [Q_{j}], F^{dist}, w_{base}, w_{eq}^{1}, \dots, w_{eq}^{n_{eq}}, w_{dif}^{1}, \dots, w_{dif}^{n_{dif}}, b_{eq}^{1}, \dots, b_{eq}^{n_{eq}}, b_{dif}^{1}, \dots, b_{dif}^{n_{dif}}) \end{matrix}$ where $[w]$ encodes the weight of the edge $(i, j)$ from the donor of patient-donor pair $P_{i}$ to the patient of pair $P_{j}$ with $i \neq j$ .

Gate 3

$ρ_{PRIO}$

Gate 3 contains the specification of gate $ρ_{PRIO}$ which implements functionality $G_{PRIO}$ (cf. Functionality 3). In the first part of the gate, we compute the weight for the different equality criteria. For each criterion k, we compute the dot product of the corresponding binary indicator vectors $[{EQ}_{i}^{k}]$ and $[{EQ}_{j}^{k}]$ . This yields the number of entries $l_{k}$ for which $[{EQ}_{i}^{k} (l_{k})] = [{EQ}_{j}^{k} (l_{k})] = [1]$ , i.e., those properties which both the donor of patient-donor pair $P_{i}$ and the patient of pair $P_{j}$ possess. Afterwards, we check whether this number is below/above/equal to the pre-defined bound $b_{eq}^{k}$ for criterion k. Then, we just sum up the weights $w_{eq}^{k}$ for all equality criteria k for which the condition $δ_{eq}^{k}$ holds. For each difference criterion k, we compute the squared difference between the values $[{dif}_{i}^{k}]$ and $[{dif}_{j}^{k}]$ . This is more efficient than computing the absolute difference. Since we compute the squared difference, we also have to check if the result is smaller/larger/equal to the squared bound $b_{dif}^{k}$ for criterion k. Similar to the equality criteria, we add up the weights $w_{dif}^{k}$ for all difference criteria k for which the condition $δ_{dif}^{k}$ holds. To compute the weight for the travel distance, we use the secret indices $[{hp}_{i}]$ and $[{hp}_{j}]$ to obtain the corresponding entry in the distance matrix $F^{dist}$ . Finally, we sum up the base weight $w_{base}$ , the pre-score ${ps}_{j}$ of the patient of patient-donor pair $P_{j}$ , and all previously computed weights. This yields the overall weight $[w]$ of the edge from the donor of pair $P_{i}$ to the patient of pair $P_{j}$ . Note that the impact of each individual criterion k on the computed weight $[w]$ can be defined by choosing the public values for $w_{base}$ , $F^{dist}$ , $w_{eq}^{k}$ , and $w_{dif}^{k}$ as well as the pre-defined formula for computing the pre-score ${ps}_{j}$ appropriately.

The correctness of gate $ρ_{PRIO}$ follows directly from the construction of the inputs for the different prioritization criteria and the correctness of the gates that are called during the execution of gate $ρ_{PRIO}$ .

Theorem 10.

Gate $ρ_{PRIO}$ (cf. Gate 3 ) securely implements functionality $G_{PRIO}$ (cf. Functionality 3 ).

The proof of Theorem 10 can be found in Appendix C.3.

4.3. Complexity analysis

The complexities of the gate $ρ_{PRIO}$ are dominated by the calls to the comparison gate for the equality and difference criteria and by the secret lookup of the travel distance. This leads to an overall communication complexity of $O ((n_{eq} + n_{dif} + | F^{dist} |^{2}) \cdot | P |^{2} \cdot s)$ and a round complexity of $O (log log | F^{dist} |)$ since all loops can be executed in parallel. Note that the computation of the pre-score ${ps}_{j}$ and thereby all criteria that belong to this category do not influence the complexity of the gate $ρ_{PRIO}$ .

5. Privacy-preserving protocols for solving the kidney exchange problem

In this section, we present three different privacy-preserving protocols for solving the KEP. The protocol $π_{KEP - RND}$ (Section 5.1) was first presented in [17] based on homomorphic encryption in a fully distributed setting where each patient-donor pair has to participate in the protocol execution. We present the protocol in the client-server model, where the patient-donor pairs (clients) use secret sharing to provide their private input to the computing peers (servers), who then execute the SMPC protocol among each other. Furthermore, we extend the original protocol such that it also allows for prioritization as defined in Section 4. The protocol $π_{KEP - IP}$ (Section 5.2) was first presented in [14]. As for the protocol $π_{KEP - RND}$ , we extend the original version such that it allows for prioritization. Finally, the protocol $π_{KEP - DP}$ (Section 5.3) is a novel protocol that is based on dynamic programming which is a brute force technique for solving integer programs. This protocol also supports prioritization. Note that in the basic version of each protocol, we only consider exchange cycles since many kidney exchange platforms do not consider exchange chains as altruistic donors are not legal in the respective country. At the end of each section, we then describe how the protocol can be extended such that it also allows for altruistic donors and exchange chains.

5.1. Protocol $π_{KEP - RND}$

In this section, we present the protocol $π_{KEP - RND}$ which is an adaption of the protocol from [17]. Note that the protocol from [17] in turn is based on the SMPC protocol for multi-party bartering from [40].

5.1.1. Approach and ideal functionality

The idea of the protocol $π_{KEP - RND}$ is to evaluate the compatibility graph $G^{C}$ against all possible constellations of exchange cycles that exist between the patient-donor pairs. The output then is one constellation of maximum weight chosen uniformly at random from all constellations of maximum weight.

We encode an exchange constellation in form of a so-called exchange constellation graph $G^{E C}$ .

Definition 11 ( $G^{EC}$ : Exchange Constellation Graph [17]).

An exchange constellation graph $G^{EC}$ is a directed graph $G^{EC} = (V, E)$ with $V : = P$ where $\forall i \in V : (d e g^{+} (i) = d e g^{-} (i) = 1) \lor (d e g (i) = 0)$ .

An exchange constellation graph encodes one possible constellation of exchanges which could exist among the patient-donor pairs. Compared to the compatibility graph, there are two major differences. First, an exchange constellation graph is independent of a specific set of patient-donor pairs whereas the compatibility graph is computed based on the input of a particular set of pairs. Second, an exchange constellation graph only contains disjoint cycles whereas the compatibility graph may also contain cycles which are not simultaneously executable. The set of all exchange constellation graphs for a set of patient-donor pairs is denoted by $G^{EC}$ and $G_{(λ)}^{EC}$ denotes the set that contains all cycles up to size λ.

For each exchange constellation graph, the protocol $π_{KEP - RND}$ checks if it is executable for the compatibility graph and then chooses one executable exchange constellation graph that maximizes the overall weight of all included exchanges. Thereupon, each patient-donor pair is provided with its corresponding exchange partners in this graph. These exchange partners are encoded by the so-called neighborhood constellation of the pair in the chosen exchange constellation graph.

Definition 12 (Neighborhood Constellation [17]).

Given an exchange constellation graph $G^{EC} = (V, E)$ , for each node $i \in V$ its neighborhood constellation is defined as $N_{d, r}^{i} (G^{EC}) = (N_{d}^{i} (G^{EC}), N_{r}^{i} (G^{EC}))$ . The source node of the incoming edge is referred to as the donating neighbor $N_{d}^{i} (G^{EC}) : = j$ if $\exists (j, i) \in E$ and $N_{d}^{i} (G^{EC}) : = 0$ , otherwise. Similarly, the target node of the outgoing edge is referred to as the receiving neighbor $N_{r}^{i} (G^{EC}) : = j$ if $\exists (i, j) \in E$ and $N_{r}^{i} (G^{EC}) : = 0$ , otherwise.

The set of all neighborhood constellations of a node i and a set of exchange constellation graphs $G^{EC}$ is denoted by $N_{d, r}^{i} (G^{EC})$ . Intuitively, the neighborhood constellation $N_{d, r}^{i} (G^{EC})$ indicates the patient-donor pair from which the patient of pair $P_{i}$ receives a kidney transplant as well as the patient-donor pair to whose patient the donor of pair $P_{i}$ donates her kidney.

The corresponding ideal functionality $F_{KEP - RND}$ that is implemented by the protocol $π_{KEP - RND}$ then outputs a number $l^{*}$ that encodes the neighborhood of all patient-donor pairs $P_{i}$ ( $i \in P$ ) in the chosen exchange constellation graph.

Functionality 4 ( $F_{KEP - RND}$ – Solving the KEP with Random Selection, based on [17]).

Let all computing peers hold shares of the secret quotes $[Q_{i}]$ containing the medical data of the patient-donor pairs $P_{i}$ ( $i \in P$ ) as defined in Functionality 1 and Functionality 3 . The input $[U_{i}]$ is a vector of secret primes, mapping a unique prime to each neighborhood constellation. Further, let $G^{EC}$ be a publicly known set of exchange constellation graphs for the parties $P_{i}$ with $i \in P$ . Then, functionality $F_{KEP - RND}$ is given as $\begin{matrix} [l^{*}] \leftarrow F_{KEP - RND} ([Q_{1}], \dots, [Q_{| P |}], [U_{1}], \dots, [U_{| P |}], G^{EC}), \end{matrix}$ where $l^{*}$ is a prime number product that encodes the neighborhood $N_{d, r}^{i} (G^{EC})$ for each patient-donor pair $P_{i}$ in an exchange constellation graph $G^{EC}$ that maximizes the overall weight of the transplants that can be executed between the patient-donor pairs. If there are multiple graphs of maximum weight, one is chosen uniformly at random and if there is no exchange constellation graph that is executable, $[l^{*}] = [0]$ stating that no $G^{EC}$ has been chosen.

5.1.2. Protocol specification

Protocol 1 contains the specification of the protocol $π_{KEP - RND}$ that implements functionality $F_{KEP - RND}$ (cf. Functionality 4). Prior to the protocol execution, each patient-donor pair $P_{i}$ ( $i \in P$ ) is given a set $I^{(i)}$ that contains $| N_{d, r}^{i} (G_{(λ)}^{EC}) | = {(| P | - 1)}^{2} + 1$ unique prime numbers (i.e., $I^{(i)} \cap I^{(j)} = \emptyset$ for all $i, j \in P$ and $i \neq j$ ). Each pair $P_{i}$ assigns a unique prime number to each possible neighborhood constellation which the pair can have in any exchange constellation graph from $G_{(λ)}^{EC}$ . This yields a total of ${(| P | - 1)}^{2} + 1$ unique primes since the neighborhood can be any combination of donor and recipient from the other patient-donor pairs plus the empty constellation, which indicates that a pair does not participate in any exchange. Note that the actual set of primes belonging to a particular pair can be publicly known. The security of the construction solely relies on the fact that the mapping of these prime numbers to the specific neighborhood constellations remains private. Further note that this construction requires $Z_{M}$ to be chosen such that it encodes at least $| P | \cdot ({(| P | - 1)}^{2} + 1)$ unique prime numbers.

The pairs then use secret sharing to provide the compute peers with shares of their private input quote $[Q_{i}]$ and a vector $[U_{i}]$ that maps each exchange constellation graph $G^{EC} \in G_{(λ)}^{EC}$ to the secret prime that encodes the patient-donor pair’s neighborhood in $G^{EC}$ .

Protocol 1

$π_{KEP - RND}$

Construction phase. The computing peers construct the secret compatibility graph encoded by the secret adjacency matrix $[A]$ using the gate $ρ_{COMP - CHECK}$ (cf. Protocol 1) such that $A (i, j) = 1$ if the donor of patient-donor pair $P_{i}$ is medically compatible with the patient of pair $P_{j}$ . Otherwise, $A (i, j) = 0$ . Furthermore, they construct the prioritization matrix $[W]$ that encodes the weight of each edge in the compatibility graph $G^{C}$ . The corresponding weight is computed using the gate $ρ_{PRIO}$ (cf. Protocol 3).

Evaluation phase. The computing peers evaluate for each exchange constellation graph $G_{k}^{EC} \in G_{(λ)}^{EC}$ whether it is executable given the current compatibility graph $G^{C}$ induced by the secret medical inputs of the patient-donor pairs. Recall that $G_{(λ)}^{EC}$ contains all exchange constellation graphs containing exchange cycles up to size λ. To check whether a particular exchange constellation graph $G_{k}^{EC}$ is executable given $G^{C}$ , it is sufficient to verify that $G_{k}^{EC}$ is a subgraph of $G^{C}$ . In particular, it has to be ensured that all edges $(u, v) \in G^{EC}$ are also present in $G^{C}$ . To this end, the computing peers compute the product of all entries of the secret adjacency matrix A corresponding to edges in $G_{k}^{EC}$ . To ensure that the overall weight of the chosen exchange constellation is maximized, the result is multiplied with the sum of the weights of all edges in $G_{k}^{EC}$ . Afterwards, we have that $L (k) = \sum_{(u, v) \in E_{k}} W (u, v)$ if $G_{k}^{EC}$ is a subgraph of $G^{C}$ and $L (k) = 0$ , otherwise. Thus, the k-th entry of L encodes the overall weight of the cycles in $G_{k}^{EC}$ . At the end of this phase, the computing peers create a product of prime numbers $[U] (k)$ for each exchange constellation graph $G_{k}^{EC}$ . For each patient-donor pair $P_{i}$ , they contribute exactly one prime number $[U_{i}] (N_{d, r}^{i} (G_{k}^{EC})$ , encoding the neighborhood constellation of $P_{i}$ in $G_{k}^{EC}$ . This allows the patient-donor pairs afterwards to derive their neighborhood constellation in the exchange constellation that is chosen during the selection phase without learning anything else about the chosen exchange constellation. Note that this construction requires the modulus M to be large enough such that the product of prime numbers is smaller than the maximum possible positive value that can be represented in $Z_{M}$ .

Shuffling phase. The two vectors $[L]$ and $[U]$ are shuffled at random using the same permutation σ. This is necessary to ensure that afterwards the entries $L (k)$ and $U (k)$ still refer to the same exchange constellation graph $G_{k}^{EC}$ . The shuffling guarantees that the selection of the exchange constellation graph is not biased by the index of the corresponding exchange constellation graph, i.e., it ensures that the exchange constellation graph that is chosen in the selection phase, is chosen uniformly at random from all exchange constellation graphs of maximum weight.

Selection phase. The computing peers iterate over all exchange constellation graphs and obliviously choose one of maximum weight. In each iteration, the k-th entry of the vector $[L^{'}]$ is compared to the $k + 1$ -th entry of $[L^{'}]$ . The entry $[L^{'}] (k + 1)$ is then set to the larger of both values. Analogously, the corresponding entries of the prime product vector $[U^{'}]$ are swapped. As $[L^{'}] (k)$ encodes the weight of $G_{k}^{EC}$ , the entry $[L^{'}] (| L^{'} | - 1)$ afterwards contains a value that is larger or equal to all other values in $[L^{'}]$ . Since we shuffled the entries of $[L^{'}]$ and $[U^{'}]$ uniformly at random in the previous phase, the entry $[L^{'}] (| L^{'} | - 1)$ is also chosen uniformly at random from all maximum values in $[L^{'}]$ . Thus, the entry $[U^{'}] (| U^{'} | - 1)$ contains the prime number product encoding the neighborhoods of the patient-donor pairs for an exchange constellation graph of maximum weight. If there are multiple such graphs, the shuffling phase ensures that one of these is chosen uniformly at random. Then, it is checked whether there is actually a graph of weight greater or equal to 0, i.e., if there is an exchange constellation graph that is executable given the compatibility graph $G^{C}$ . If there is such a graph, the output $l^{*}$ is set to the corresponding prime number product encoded by $[U^{'}] (| U^{'} | - 1)$ . Otherwise, $l^{*}$ is set to $[0]$ stating that no exchange constellation graph was chosen. This holds since only a patient-donor pair itself knows the mapping between its prime numbers $U_{i}$ and its possible neighborhood constellations. The other patient-donor pairs are able to determine the prime number for each other pair but they are not able to link it to a neighborhood constellation.

Output reconstruction. After the protocol execution, the computing peers provide the patient-donor pairs with their shares of $[l^{*}]$ . Each pair $P_{i}$ ( $i \in P$ ) uses the shares to determine the value $l^{*}$ . If $l^{*} = 0$ , they know that no exchange constellation graph was chosen. Otherwise, they check which of their prime numbers divides $l^{*}$ and thereby determine their neighborhood in the chosen exchange constellation graph. Note that they only learn their respective exchange partners $D (i) : = N_{d}^{i}$ and $R (i) = N_{r}^{i}$ but not the exchange constellation graph that was chosen. In particular, each pair only learns its own neighborhood constellation without learning anything on other edges in the chosen exchange constellation graph.

Correctness. In order to show the correctness of protocol $π_{KEP - RND}$ , we have to show that its output distribution is statistically indistinguishable from the output distribution of functionality $F_{KEP - RND}$ . We distinguish two cases. In the first case, none of the exchange constellation graphs $G_{k}^{EC} \in G_{(λ)}^{EC}$ is executable for the given compatibility graph and the output of $F_{KEP - RND}$ is fixed, i.e., $[l^{*}] = [0]$ , which indicates that no exchange constellation is chosen at all. In that case, all entries of the vectors $[H]$ and $[L]$ computed in the evaluation phase are equal to $[0]$ since there is no $G_{k}^{EC} \in G_{(λ)}^{EC}$ such that $G_{k}^{EC}$ is a subgraph of $G^{C}$ . Thereby, also all entries of the vector $[L^{'}]$ are equal to $[0]$ and thus $[l^{*}] = [0]$ .

In the second case, there is at least one $G_{k}^{EC} \in G_{(λ)}^{EC}$ such that $G_{k}^{EC}$ is a subgraph of $G^{C}$ . In that case we have to show that protocol $π_{KEP - RND}$ chooses one exchange constellation of maximum weight uniformly at random from all constellations of maximum weight.

Observe that after the evaluation phase, $[L] (k)$ encodes the weight of each $G_{k}^{EC} \in G_{(λ)}^{EC}$ . Prior to the selection phase, we shuffle the entries of the vector $[L]$ uniformly at random, obtaining the vector $[L^{'}]$ . In the selection phase, we then bubble up the entry with the smallest index among all entries of maximum weight from $[L^{'}]$ . Together with the shuffling of $[L^{'}]$ , the value $[L^{'}] (| L^{'} | - 1)$ thus encodes the weight of one exchange constellation chosen uniformly at random from all exchange constellations of maximum weight. Since all modifications (shuffle and swap operations) that are applied to $[L^{'}]$ are also applied to the vector $[U^{'}]$ encoding the prime number products, $[U^{'}] (| U^{'} | - 1)$ encodes the prime number product for an exchange constellation of maximum weight, chosen uniformly at random from all constellations of maximum weight. Thus, protocol $π_{KEP - RND}$ correctly implements functionality $F_{KEP - RND}$ .

Theorem 13.

Protocol $π_{KEP - RND}$ (cf. Protocol 1 ) securely implements functionality $F_{KEP - RND}$ (cf. Functionality 4 ).

Proof (sketch).

We sketch a simulator $S$ which outputs a transcript that is statistically indistinguishable from the view ${VIEW}_{I_{C}}^{π} (\overline{x})$ of the corrupted parties $I_{C}$ . The detailed description of $S$ is provided in Simulator 4, Appendix C.

Recall that in order to simulate the call to a gate, the simulator $S$ has to simulate input and output to the gate and then call the simulator of the gate on these values. Thus, $S$ first sets $⟨ [A] ⟩ \leftarrow_{$} Z_{M}^{| P | \times | P |}$ and $⟨ [W] ⟩ \leftarrow_{$} Z_{M}^{| P | \times | P |}$ . Then, $S$ calls the simulators of the gates $ρ_{COMP - CHECK}$ and $ρ_{PRIO}$ on input $[Q_{i}]$ , $[Q_{j}]$ and output $⟨ [A] ⟩$ and $⟨ [W] ⟩$ , respectively.

The computation of the product over the edges in the adjacency matrix $[A]$ at the beginning of the evaluation phase is simulated by repeatedly calling the simulator of the multiplication gate on input $⟨ [A] (u, v) ⟩$ for $(u, v) \in E_{k}$ , using random shares from $Z_{M}$ for the output, i.e., $⟨ [H] (k) ⟩ \leftarrow_{$} Z_{M}$ . Similarly, the entries of the vector $[L]$ are simulated by calling the simulator of the multiplication gate on input $⟨ [H] (k) ⟩$ , $\sum_{(u, v) \in E_{k}} ⟨ [W] (u, v) ⟩$ and output $⟨ [L] (k) ⟩ \leftarrow_{$} Z_{M}$ . The computation of the product of prime numbers in Step 8 is then simulated analogous to the product over the entries of the adjacency matrix in Step 6.

At the beginning of the shuffling phase, $S$ calls the simulator of the gate $ρ_{GEN - PERM}$ on input $| G_{(λ)}^{EC} |$ and output $⟨ [σ] ⟩$ . The remainder of the shuffling phase is simulated by calling the simulator of the gate $ρ_{SHUFFLE}$ once on input $⟨ [L] ⟩$ , $⟨ [σ] ⟩$ and output $⟨ [L^{'}] ⟩ \leftarrow_{$} Z_{M}^{| G_{(λ)}^{EC} |}$ , and once on input $⟨ [U] ⟩$ , $⟨ [σ] ⟩$ and output $⟨ [U^{'}] ⟩ \leftarrow_{$} Z_{M}^{| G_{(λ)}^{EC} |}$ .

In order to simulate the call to the comparison gate at the beginning of the selection phase, $S$ calls the simulator of the comparison gate on input $⟨ [L^{'}] (k) ⟩$ , $⟨ [L^{'}] (k + 1) ⟩$ and output $⟨ [b] ⟩ \leftarrow_{$} Z_{M}$ . In a similar fashion, $S$ simulates the two calls to the selection gate in Steps 14 and 15, using the previously simulated values as inputs and random shares from $Z_{M}$ as output. The value $[c]$ is then simulated by calling the simulator of the comparison gate on input $⟨ [L^{'}] (| L^{'} | - 1) ⟩$ , $⟨ [0] ⟩$ and output $⟨ [c] ⟩ \leftarrow_{$} Z_{M}$ . Finally, the simulator sets $⟨ [l^{*}] ⟩ : = [l^{*}]$ and calls the simulator of the selection gate on input $⟨ [c] ⟩$ , $⟨ [U^{'}] (| U^{'} | - 1) ⟩$ , $⟨ [0] ⟩$ and output $⟨ [l^{*}] ⟩$ .

Since all gates that are called during the execution of $π_{KEP - RND}$ have already been shown to be secure in the semi-honest security model and due to the properties of the underlying secret sharing scheme, $S$ creates a view that is statistically indistinguishable from ${VIEW}_{I_{C}}^{π}$ . □

5.1.3. Complexity analysis

The two dominant phases of protocol $π_{KEP - RND}$ are the evaluation and the selection phase. The loop in the evaluation phase is executed $| G_{(λ)}^{EC} |$ times and in each iteration the most costly step is the computation of the products over the edges in $[A]$ and the secret primes requiring $log (| E_{k} |)$ and $log (| P |)$ multiplications, respectively. The $| G_{(λ)}^{EC} |$ iterations of the outer loop can be executed in parallel. Thus, this phase has communication complexity $O ((log (| E_{k} |) + log (| P |)) \cdot | G_{(λ)}^{EC} | \cdot s)$ and round complexity $O (log (| E_{k} |) + log (| P |))$ . The selection phase then requires $| G_{(λ)}^{EC} | - 1$ comparisons and $2 \cdot (| G_{(λ)}^{EC} | - 1)$ multiplications leading to communication complexity $O (| G_{(λ)}^{EC} | \cdot s)$ and round complexity $O (| G_{(λ)}^{EC} |)$ . Thus, overall the protocol has communication complexity $O ((log (| E_{k} |) + log (| P |)) \cdot | G_{(λ)}^{EC} | \cdot s)$ and round complexity $O (| G_{(λ)}^{EC} |)$ since $| G_{(λ)}^{EC} |$ is always larger than $log (| P |)$ and $log (E_{k})$ .

5.1.4. Extension for exchange chains

Protocol $π_{KEP - RND}$ can be modified such that it also considers altruistic donors and exchange chains. To this end, the set of input peers is extended by the altruistic donors, i.e., instead of the input peers $P_{i}$ ( $i \in P$ ), we now have $P_{i}$ ( $i \in P \cup A$ ). Each input peer then also inputs a secret bit $A (i)$ indicating whether it is an altruistic donor or a regular patient-donor pair. Note that regular patient-donor pairs and altruistic donors are treated exactly the same in the protocol. This is necessary to keep private whether an input peer is a patient-donor pair or an altruistic donor. In the following, we describe the changes that have to be applied to each phase resulting in the extended protocol $π_{KEP - RND - CC}$ that considers exchange cycles and chains. For completeness, we also provide the detailed specification of the extended protocol $π_{KEP - RND - CC}$ in Appendix B (Protocol 4).

Construction phase. We do not have to apply any direct changes to the construction phase. However, the medical input data of the “patient” of an altruistic donor has to be set to 0. Thereby, we obtain an adjacency matrix A where for an altruistic donor $P_{i}$ all entries $A (j, i)$ ( $j \in P \cup A$ ) are equal to 0 and all entries $A (i, j)$ ( $j \in P$ ) indicate the medical compatibility between the altruistic donor $P_{i}$ and the patient of patient-donor pair $P_{j}$ .

Table 2
Size of the set $G_{(3)}^{EC}$ including all exchange constellations for cycles up to size 3 compared to the size of the set $G_{(3, \infty)}^{EC}$ including all exchange constellations for cycles up to size 3 and for chains of unbounded size

$| P \cup A |$ 3 4 5 6 7 8 9 10

$| G_{(3)}^{EC} |$ 5 17 65 275 1211 5915 31067 171575

$| G_{(3, 3)}^{EC} |$ 17 77 485 3095 21203 167868 1370267 12009455

$| G_{(3, 4)}^{EC} |$ 17 101 605 4535 36323 319068 3021371 31242095

$\| P \cup A \|$	3	4	5	6	7	8	9	10
$\| G_{(3)}^{EC} \|$	5	17	65	275	1211	5915	31067	171575
$\| G_{(3, 3)}^{EC} \|$	17	77	485	3095	21203	167868	1370267	12009455
$\| G_{(3, 4)}^{EC} \|$	17	101	605	4535	36323	319068	3021371	31242095

Evaluation phase. The inclusion of exchange chains has a major impact on the set of all exchange constellation graphs $G^{EC}$ as there are many more exchange chains than cycles. For example, for every cycle $(1, 2, 3)$ of size 3, there are already three different exchange chains $(1, 2, 3)$ , $(2, 3, 1)$ , and $(3, 1, 2)$ where the first entry in a chain always corresponds to the altruistic donor. Furthermore, some countries even allow a maximum chain length of $κ = 4$ [6,10]. Thus, the set $G_{(λ)}^{EC}$ is significantly larger if also exchange chains are considered. This means that the number of iterations that are required in the evaluation phase also increases significantly. Note, however, that all these iterations can still be performed in parallel. Table 2 shows the size of the set $G_{(3)}^{EC}$ for exchange cycles up to size 3 compared to the size of the sets $G_{(3, 3)}^{EC}$ and $G_{(3, 4)}^{EC}$ for exchange cycles up to size 3 and exchange chains up to length 3 and 4, respectively.

Besides the number of iterations, also the steps that have to be performed in each iteration change slightly. Recall that the vector H states for each $G^{EC} \in G_{(λ, κ)}^{EC}$ whether it is executable under the compatibility graph encoded by A. If exchange chains are added, we now additionally have to check for each chain in $G^{EC}$ whether it starts with an altruistic donor. To this end, we just multiply the altruist bit $A (i)$ for the corresponding input peer to the entry of H. Thereby, it is guaranteed that an exchange chain is only considered executable if all its edges are present in A and if the altruist bit for the node corresponding to the first entry in the chain is equal to 1. The remainder of the evaluation phase stays the same as for the protocol for exchange cycles only.

Shuffling phase and selection phase. These phases stay exactly the same as for the protocol without exchange chains except for the fact that the set of exchange constellation graphs is now considerably larger. Since the iterations of the selection phase cannot be executed in parallel, this has a significant impact on the runtime of this phase. We show this impact in the evaluation of our protocols (cf. Section 6).

Security and complexity. We omit a security proof for the protocol $π_{KEP - RND - CC}$ as it is trivial to prove the security of the modifications which we applied to the protocol $π_{KEP - RND}$ . Similarly, the complexity analysis is the same as for the protocol $π_{KEP - RND}$ except that the set $G_{(λ, κ)}^{EC}$ is considerably larger than $G_{(λ)}^{EC}$ .

5.2. Protocol

π_{KEP - IP}

In this section, we present the protocol $π_{KEP - IP}$ which extends the protocol from [14] for solving the KEP using privacy-preserving integer programming such that it can also provide for prioritization.

5.2.1. Approach and ideal functionality

The protocol $π_{KEP - IP}$ is based on the Branch-and-Bound algorithm [29] which is a common algorithm for IP. The Branch-and-Bound algorithm solves the problem of fractional solutions that can occur when solving the LP relaxation of the subset formulation using an LP solver such as the Simplex algorithm [22]. Such fractional solutions are not acceptable for the KEP since a cycle can either be part of the solution or not, i.e., a variable can either have value 1 or 0.

The main idea of the Branch-and-Bound algorithm is to create a tree of subproblems which are repeatedly solved using an LP solver. A node in the tree contains an upper bound on the solutions in that branch and the currently best known integral solution (called the incumbent $X^{*} \in Z^{n}$ and its value $z^{*} \in R$ ). The protocol $π_{KEP - IP}$ uses the SMPC protocol from [37] to solve the LP at each node. This protocol relies on the Simplex algorithm which is the most common method for solving LPs [35]. Algorithm 1 contains pseudocode for the Branch-and-Bound algorithm.

Algorithm 1

Branch-and-bound algorithm, based on [14,29]

The performance of the Branch-and-Bound algorithm relies on the repeated pruning of branches in the tree of subproblems that cannot further improve the solution $X^{*}$ . In order to preserve this property in the privacy-preserving setting, we make the pruning decisions and thus the structure of the Branch-and-Bound tree $B$ publicly known, i.e., we include them in the output of the corresponding ideal functionality. In particular, the output of the ideal functionality has to include the structure of the Branch-and-Bound tree $B$ as well as the number of Simplex iterations $I$ required for solving each of the subproblems in $B$ . The latter is required since the existing protocols for the Simplex algorithm (e.g., [20,37]) include the number of Simplex iterations $I$ required to solve the LP in the output of the ideal functionality. Note that in [15] it is empirically shown that the inclusion of $B$ and $I$ in the output of the ideal functionality does not allow for the derivation of any additional sensitive patient-donor information, i.e., information that can be linked directly to the private input and output of particular patient-donor pairs. However, it is also shown that it is possible to derive some structural information on the problem instance as a whole from $B$ and $I$ . For example, $I$ correlates with the number of transplants that can be found. Furthermore, [15] shows possible strategies for limiting the amount of information that is revealed on $B$ and $I$ . For details on the empirical analysis, we refer the reader to [15].

Functionality 5 contains the definition of the ideal functionality implemented by protocol $π_{KEP - IP}$ .

Functionality 5 (

F_{KEP - IP}

– Solving the KEP using Integer Programming, based on [14]).

Let all computing peers hold their respective shares of the secret quotes $[Q_{i}]$ containing the medical data of the patient-donor pairs $P_{i}$ ( $i \in P$ ) as defined in Functionality 1 and Functionality 3 . Then, functionality $F_{KEP - IP}$ is given as $\begin{matrix} (([d_{1}], [r_{1}]), \dots, ([d_{| P |}], [r_{| P |}]), B, I) \leftarrow F_{KEP - IP} ([Q_{1}], \dots, [Q_{| P |}]), \end{matrix}$ where $B$ is the structure of the Branch-and-Bound tree, $I$ contains the necessary number of Simplex iterations for solving the subproblems in the tree, and $(d_{i}, r_{i})$ are the indices of the donor and recipient for patient-donor pair $P_{i}$ for a set of exchange cycles that maximize the overall weight of the transplants that can be executed between the patient-donor pairs $P_{i}$ ( $i \in P$ ). The set of cycles corresponds to the output of Algorithm 1 on input of the set $S$ using the Simplex implementation from [ 37 ] to solve the subproblems in $B$ . The set $S$ is structured such that it contains all subsets of size 2 permuted uniformly at random followed by all subsets of size 3 permuted uniformly at random.

5.2.2. Protocol specification

Protocol 2 contains the specification of the protocol $π_{KEP - IP}$ . Similar to the protocol $π_{KEP - RND}$ (cf. Protocol 1), prior to the actual protocol execution each patient-donor pair $P_{i}$ ( $i \in P$ ) sends shares of the relevant medical data of its patient and donor to the computing peers. After the protocol execution, the computing peers then provide each patient-donor pair $P_{i}$ ( $i \in P$ ) with the shares of their computed exchange partners (indicated by $D (i)$ and $R (i)$ ).

Construction phase. As in the protocol $π_{KEP - RND}$ , the computing peers first construct the adjacency matrix A and the prioritization matrix W. Afterwards, the gate $ρ_{SHUFFLE}$ is used to obliviously shuffle the entries of the matrices A and W using the same permutation σ. This guarantees unbiasedness in the sense that the index of a patient-donor pair $P_{i}$ does not influence the probability that the patient of pair $P_{i}$ receives a kidney transplant. The shuffling of the compatibility graph also makes it impossible to link an entry of the tableau T to a particular patient-donor pair.

Setup phase. We call the gate $ρ_{IP - SETUP}$ to set up the initial tableau for the subset formulation of the KEP (cf. Equation (4)). Recall that in addition to the secret initial tableau $[T]$ , the protocol $ρ_{IP - SETUP}$ also returns the matrix $[M]$ mapping each subset $S_{i} \in S$ to an exchange cycle (cf. Section 3.3). Afterwards, we establish an initial feasible solution of the LP. For the KEP, this is trivial since we can just choose the solution that does not select any subset at all, i.e., $X^{*} (i) = 0$ ( $i \in {1, \dots, | S |}$ ) and $z^{*} = 0$ . The KEP also provides us with the initial upper bound $\overline{b} = | P | \cdot ω_{max}$ corresponding to a solution where all patient-donor pairs are part of an exchange cycle and each chosen edge has maximum weight $ω_{max}$ . Based on these initial values, we add the initial problem to the list of problems L that have to be solved. Each such problem consists of an upper bound $[\overline{b}]$ , a tableau $[T]$ , a vector of partial solutions $[Q]$ containing all subsets that have already been chosen on the path from the root to the current subproblem, and a common denominator $[d]$ which is used to avoid fractional values. Since the initial problem only contains integer values, the common denominator is initially set to $[1]$ .

Protocol 2

$π_{KEP - IP}$ , based on [14]

Optimization phase. In each iteration of this phase, we choose one subproblem P from the list L until L is empty. Then, we determine if we can prune the branch emanating from the current subproblem P. To this end, we check whether the upper bound $[\overline{b}]$ is larger than the value of the currently best known solution. If this is not the case, the subtree can be pruned. Otherwise, we continue by solving the subproblem using the protocol $ρ_{SIMPLEX}$ from [37]. Thereby, we obtain the optimal solution $[X^{'}]$ of value $[z]$ . We avoid the necessity of representing fractional values by using the common denominator $[d]$ . In particular, the actual solution is $[\frac{X^{'}}{d}]$ and it has the value $[\frac{z}{d}]$ . Since the solution returned by $ρ_{SIMPLEX}$ does not contain those subsets that have already been chosen in prior subproblems of the current path in the tree, we have to include these by adding the partial solution vector $[Q]$ to the computed solution $[X^{'}]$ .

Update phase. In this phase, we use the computed solution $[X]$ to update the incumbent $[X^{*}]$ (i.e., the currently best known integer solution). Additionally, we compute the vector $[F]$ which indicates the first fractional variable if the computed solution is fractional. If the solution is not fractional, all entries of $[F]$ are $[0]$ . Since we know that $\frac{X (i)}{d}$ is in the interval $[0, 1]$ , we also know that $\frac{X (i)}{d}$ is fractional iff $X (i)$ is in the interval $(0, d)$ . We use this knowledge to avoid the costly integer division $\frac{X (i)}{d}$ and instead determine whether $[X]$ is a fractional solution using the two comparisons $X (i) > 0$ and $X < d$ . We then select the first variable for which this is the case and store it in the constraint indicator vector $[F]$ . Recall that the incumbent is only to be updated if the value z of the newly computed solution X is larger than the value $z^{*}$ of the incumbent and if X is integral. The latter is ensured by subtracting $| P | \cdot ω_{max} \cdot [d]$ (which is an upper bound on z) from $[z]$ if the constraint indicator vector $[F]$ indicates that $[X]$ is fractional. Note that $[I]$ already stores which subsets are chosen in the solution $[X]$ and can thus be used as new incumbent.

Branching phase. Since we do not know whether the incumbent was updated in the update phase, we always have to create two new subproblems. We use the constraint indicator vector $[F]$ to create two new tableaux $[T^{0}]$ and $[T^{1}]$ . In particular, we set the entries of the column of the fractional variable indicated by $[F]$ to $[0]$ and update the bounds according to the new value of this fractional variable. To this end, we first extract the column $[D]$ of the fractional variable. Then, we create a vector $[Δ_{k}^{v}]$ for each row k and each value $v \in {0, 1}$ of the fractional variable. These row vectors contain the value of the column $[D]$ at the index of the fractional variable and v at the last position for updating the bounds. All other entries of $Δ_{k}^{v}$ are equal to $[0]$ . By subtracting $Δ_{k}^{v}$ from $[T]$ , we thus obtain the new tableaux $[T^{v}]$ ( $v \in {0, 1}$ ). Finally, we extend the list L by the subproblems $([T^{0}], [z], [Q], [d])$ and $([T^{1}], [z], [Q] + [F], [d])$ .

Resolution phase. After the optimization phase, $[X^{*}]$ encodes a set of subsets that form an optimal solution to the KEP. To derive the actual exchange partners for each patient-donor pair, we first determine those exchange cycles that correspond to the subsets indicated by $X^{*}$ . These are exactly those cycles $C_{i, j}$ for which the subset $S_{i}$ was chosen and which are indicated by the mapping $[M]$ computed during the setup phase. In particular, it has to hold that $X^{*} (i) = 1$ and $M (i, j) = 1$ . We store these cycles in the matrix $[Y]$ such that $[Y] (i, j) = [1]$ iff cycle $C_{i, j}$ is chosen and $[Y] (i, j) = [0]$ , otherwise. Based on the chosen cycles, we then determine the edges of the compatibility graph that correspond to these cycles and store them in the solution matrix $[A]$ . Before deriving the indices of the exchange partners for each patient-donor pair, we revert the initial shuffling by applying the gate $ρ_{REVERSE - SHUFFLE}$ on $[A]$ . Since each patient-donor pair can at most be involved in one cycle, we know that each row and each column of $[A^{'}]$ contain at most one entry that is equal to $[1]$ whereas all other entries have to be equal to $[0]$ . Thus, we obtain the recipient for the donor of pair $P_{i}$ by summing up all entries of the i-th row multiplied by their column index j. Similarly, we compute the donor for the patient of each pair.

Correctness. In order to show the correctness of protocol $π_{KEP - IP}$ , we have to show that its output distribution is indistinguishable from the output distribution of functionality $F_{KEP - IP}$ (cf. Functionality 5). Since the optimization, update, and branching phase of protocol $π_{KEP - IP}$ follow the procedure specified in Algorithm 1, it holds that $[X^{*}]$ encodes a set of subsets of maximum weight. Thus, we only have to show that the construction phase and setup phase yield the correct input for the subsequent phases and that the resolution phase yields the correct exchange partners for each patient-donor pair for the set of subsets computed in the previous phases.

For the input, we thus have to show that $[T]$ encodes the initial tableau for the subset formulation, where the set $S$ is ordered such that it contains a uniform random permutation of all subsets of size 2 followed by a uniform random permutation of all subsets of size 3. Observe that the matrices $[A]$ and $[W]$ that encode the compatibility graph are randomly shuffled with permutation σ previous to the setup phase. This implies that the order of the patient-donor pairs is also shuffled with σ. Thus, during the execution of the gate $ρ_{IP - SETUP}$ a tableau $[T]$ is created for the randomly permuted set of patient-donor pairs. This implies that each node i in a subset $S \in S$ corresponds to the patient-donor pair with index $σ^{- 1} (i)$ . Thus, the tableau that is returned by the gate $ρ_{IP - SETUP}$ encodes the initial tableau for the subset formulation, where $S$ contains a random permutation of all subsets of size 2 followed by a random permutation of all subsets of size 3. The same also holds for the mapping $[M]$ between the subsets and the potential cycles for each subset.

It remains to show that the resolution phase correctly transforms the set of chosen subsets encoded by $[X^{*}]$ into the corresponding exchange partners for each patient-donor pair. However, this directly follows from the description of the resolution phase above.

Thus, the protocol $π_{KEP - IP}$ correctly implements functionality $F_{KEP - IP}$ .

Theorem 14.

Protocol $π_{KEP - IP}$ (cf. Protocol 2 ) securely implements functionality $F_{KEP - IP}$ (cf. Functionality 5 ).

Proof (sketch).

The construction of the adjacency matrix $[A]$ and the prioritization matrix $[W]$ are simulated as for the protocol $π_{KEP - RND}$ (cf. Theorem 13). To simulate the shuffling of the compatibility graph, $S$ calls the simulator of the gate $ρ_{GEN - PERM}$ on input $| G_{(λ)}^{EC} |$ and output $⟨ [σ] ⟩$ as well as the simulator of the gate $ρ_{SHUFFLE}$ once on input $⟨ [A] ⟩$ , $⟨ [σ] ⟩$ and output $⟨ [A^{'}] ⟩ \leftarrow_{$} Z_{M}^{| P | \times | P |}$ , and once on input $⟨ [W] ⟩$ , $⟨ [σ] ⟩$ and output $⟨ [W^{'}] ⟩ \leftarrow_{$} Z_{M}^{| P | \times | P |}$ .

In order to simulate the call to the gate $ρ_{IP - SETUP}$ , the simulator $S$ sets $⟨ [T] ⟩ \leftarrow_{$} Z_{M}^{(| P | + 1) \times (| S | + | P | + 1)}$ and $⟨ [M] ⟩ \leftarrow_{$} Z_{M}^{| S | \times λ_{max}}$ . Then, $S$ calls the simulator of $ρ_{IP - SETUP}$ on input $⟨ [A^{'}] ⟩$ , $⟨ [W^{'}] ⟩$ and output $⟨ [T] ⟩$ , $⟨ [M] ⟩$ . The remaining steps of the setup phase are simulated by just executing Steps $8 - 13$ as specified in Protocol 2.

Since the simulator knows the structure of the Branch-and-Bound tree $B$ , he also knows the number of iterations of the while loop in the optimization phase and the number of problem instances contained in the list L at the beginning of each iteration. Thus, $S$ simulates the while loop by executing it for the number of iterations indicated by $B$ . At the beginning of each iteration, $S$ chooses the next instance from L and updates L following the specification of Protocol 2. Then, $S$ calls the simulator of the multiplication gate once on input $⟨ [\overline{b}] ⟩$ , $⟨ [d^{*}] ⟩$ and output $⟨ [t_{0}] ⟩ \leftarrow_{$} Z_{M}$ , and once on input $⟨ [z^{*}] ⟩$ , $⟨ [d] ⟩$ and output $⟨ [t_{1}] ⟩ \leftarrow_{$} Z_{M}$ . Using the simulated values for $[t_{0}]$ and $[t_{1}]$ , $S$ calls the simulator of the comparison gate on input $⟨ [t_{0}] ⟩$ , $⟨ [t_{1}] ⟩$ and output $⟨ [t] ⟩ \leftarrow_{$} Z_{M}$ . In the next step, $S$ has to simulate the recovering of the plaintext value t from the secret shared value $[t]$ . Besides the number of iterations of the while loop, the structure of the Branch-and-Bound tree $B$ also tells the simulator, which subproblems in $B$ can be pruned. Thus, $S$ knows the plaintext value t for each subproblem in $B$ . Based on this knowledge, $S$ sets $⟨ t ⟩ : = 0$ if $B$ indicates that the current subproblem is to be pruned and $⟨ t ⟩ : = 1$ , otherwise. Then, $S$ calls the simulator of the gate for recovering a plaintext value from a secret value on input $⟨ [t] ⟩$ and output $⟨ t ⟩$ . Note that such a gate is provided by the arithmetic black box (ABB) (cf. Section 2.2). If $B$ indicates that the current subproblem is to be pruned, the simulator continues with the next iteration of the while loop. Otherwise, the simulator continues with simulating the call to the gate $ρ_{SIMPLEX}$ by calling the corresponding simulator on input $⟨ [T] ⟩$ and output $⟨ [X^{'}] ⟩$ , $⟨ [z] ⟩$ , $⟨ [d] ⟩$ . For the security of the gate $ρ_{SIMPLEX}$ , we refer to [37]. In the next step, $S$ calls the simulator of the multiplication gate on input $⟨ [Q] (v) ⟩$ , $⟨ d ⟩$ and output $⟨ [x] ⟩ \leftarrow_{$} Z_{M}$ . Then, $S$ sets $⟨ [X] (v) ⟩ : = ⟨ [X^{'}] (v) ⟩ + ⟨ [x] ⟩$ .

All steps of the update phase and the branching phase are simulated by either executing the computations specified in Protocol 2 on the previously simulated values or by calling the simulators of the called gates, using the previously simulated values as input and random shares from $Z_{M}$ as output.

In order to simulate the resolution phase, $S$ first has to simulate the computation of each entry $[Y] (i, j)$ of the matrix $[Y]$ . To this end, $S$ calls the simulator of the multiplication gate on input $⟨ [X^{*}] (i) ⟩$ , $⟨ [M] (i, j) ⟩$ and output $⟨ [Y] (i, j) ⟩ \leftarrow_{$} Z_{M}$ . The entries of the solution matrix $[Ψ]$ are then simulated by setting $⟨ [Ψ] (v, w) ⟩ : = ⟨ [Ψ] (v, w) ⟩ + ⟨ [Y] (i, j) ⟩$ for each edge $(v, w) \in E (C_{i, j})$ . The subsequent reverse shuffling of the solution matrix, is simulated by calling the simulator of gate $ρ_{REVERSE - SHUFFLE}$ on input $⟨ [Ψ] ⟩$ , $⟨ [σ^{- 1}] ⟩$ and output $⟨ [Ψ^{'}] ⟩$ . However, the entries of $⟨ [Ψ^{'}] ⟩$ cannot be simulated using random shares from $Z_{M}$ since they are used to compute the output values $[D]$ and $[R]$ afterwards. Thus, $⟨ [Ψ^{'}] ⟩$ has to be chosen such that the simulation of $[D]$ and $[R]$ in Steps 61 and 62 yield the correct shares of the protocol output. In particular, $S$ chooses $⟨ [Ψ^{'}] ⟩$ such that $\sum_{j = 1}^{| P |} (j \times ⟨ [Ψ^{'}] (j, i) ⟩) = [D] (i)$ and $\sum_{j = 1}^{| P |} (j \times ⟨ [Ψ^{'}] (i, j) ⟩) = [R] (i)$ for $i = {1, \dots, | P |}$ . Afterwards, $S$ simulates the computation of $[D]$ and $[R]$ by executing Steps 61 and 62 as specified in Protocol 2, using the previously simulated solution matrix $⟨ [Ψ^{'}] ⟩$ .

Since all gates that are called during the execution of $π_{KEP - IP}$ have already been shown to be secure in the semi-honest security model and due to the properties of the underlying secret sharing scheme, $S$ creates a view that is statistically indistinguishable from ${VIEW}_{I_{C}}^{π}$ . □

5.2.3. Complexity analysis

The most costly operation in the protocol $π_{KEP - IP}$ is the call to the gate $ρ_{SIMPLEX}$ for each subproblem. Our implementation of the gate from [37] has communication complexity $O (m^{2} + m n + m s + n s)$ and round complexity $O (log log m)$ for an LP with m constraints and n variables. This yields the overall communication complexity $O (I \cdot (| P |^{2} + | P | \cdot | S | + | P | \cdot s + | S | \cdot s))$ and round complexity $O (log log | P |)$ since the subset formulation of the KEP has $| P | + 1$ constraints and $| P | + | S |$ variables. Note that the number of Simplex iterations $I$ is in the order of $2^{n}$ in the worst case.

5.2.4. Extension for exchange chains

Similar to the protocol $π_{KEP - RND}$ , we also extend the protocol $π_{KEP - IP}$ such that it can be used with altruistic donors and exchange chains. We refer to the resulting adapted protocol as $π_{KEP - IP - CC}$ . Since the changes that have to be applied to the protocol $π_{KEP - IP}$ essentially only are applied to the gates $ρ_{COMP - CHECK}$ and $ρ_{IP - SETUP}$ , we do not provide the specification of protocol $π_{KEP - IP - CC}$ in detail.

Construction phase. As for protocol $π_{KEP - RND - CC}$ , it is sufficient here that the medical input of the “patient” of the altruistic donor is equal to $[0]$ .

Setup phase. For the gate $ρ_{IP - SETUP}$ , we have to apply the modifications described in Section 3.3. The tableau remains the same as for the protocol for exchange cycles only with the exception that an entry $T (1, i)$ now indicates the maximum weight of an exchange cycle or chain that consists of the nodes in the subset $S_{i} \in S$ . The number of subsets also increases if the maximum chain size κ is larger than the maximum cycle size λ. Furthermore, the mapping $[M]$ that is returned by $ρ_{IP - SETUP}$ contains significantly more entries for each subset $S_{i} \in S$ . Recall that the i-th row of $[M]$ in the protocol $π_{KEP - IP}$ contains one entry for each exchange cycle that has the same nodes as $S_{i} \in S$ such that $[M] (i, j) = 1$ if the cycle $C_{i, j}$ is executable under $G^{C}$ and has maximum weight of all cycles for $S_{i}$ . If there are multiple such cycles, the first one with these properties is chosen. If we now also include exchange chains, then we have to add an entry $[M] (i, j)$ for each possible chain that consists of the nodes in the subset $S_{i}$ . This yields $| S_{i} |!$ additional entries for each subset $S_{i} \in S$ . Note that the benefit of the subset formulation (cf. Definition 7) compared to the standard cycle formulation of the KEP (cf. Definition 6) is even larger for the protocol $π_{KEP - IP - CC}$ than for the protocol $π_{KEP - IP}$ . In particular, the subset formulation now only requires a single variable to cover all chains that contain the same nodes as a subset $S_{i}$ whereas the standard formulation would require $| S_{i} |!$ variables. The remainder of the setup phase stays the same as in the protocol $π_{KEP - IP}$ . Nevertheless, the inclusion of exchange chains still comes along with a considerable overhead as all chains have to be evaluated during the setup of the initial tableau T (cf. Section 3.3).

Optimization phase. This phase stays exactly the same as for the protocol $π_{KEP - IP}$ .

Resolution phase. If the protocol also considers exchange chains, then a row in the secret mapping $[M]$ of the subsets to an exchange cycle or chain has size $λ_{i} + κ_{i}$ instead of $λ_{i}$ . This means that we have to iterate over $λ_{i} + κ_{i}$ entries for each row of $[M]$ . Apart from this, the resolution phase remains unchanged.

Security and complexity. Since the only changes that are applied to the protocol $π_{KEP - IP}$ to obtain the protocol $π_{KEP - IP - CC}$ are modifications of the gates $ρ_{COMP - CHECK}$ (cf. Section 3.2), $ρ_{IP - SETUP}$ (cf. Section 3.3), and the resolution phase, the security proof for the protocol $π_{KEP - IP - CC}$ is essentially the same as for the protocol $π_{KEP - IP}$ (cf. Theorem 16). Similarly, the complexities of the protocol $π_{KEP - IP - CC}$ are the same as for the protocol $π_{KEP - IP}$ as these are still dominated by the complexities of the optimization phase.

5.3. Protocol $π_{KEP - DP}$

In this section, we present our novel SMPC protocol $π_{KEP - DP}$ for solving the KEP with prioritization based on dynamic programming.

5.3.1. Approach and ideal functionality

The basic idea of our protocol $π_{KEP - DP}$ is to apply the general approach for dynamic programming presented in [35] to the subset formulation of the KEP (cf. Definition 7). Recall that the set $S$ contains all subsets of nodes of sizes 2 to λ where λ is the maximum cycle size. For a set of subset indices $I \subseteq {1, \dots, | S |}$ , we say that I is feasible for a node set $V^{'} \subseteq V$ if $⋂_{i \in J} S_{i} = \emptyset$ and $⋃_{i \in J} S_{i} \subseteq V^{'}$ , i.e., if all subsets indicated by I are disjoint and if they only contain nodes from $V^{'}$ . The weight of such a set of subsets is defined as the sum of the weights of the individual subsets (i.e., $ω (I) : = \sum_{i \in I} ω (S_{i})$ ). We then define the maximum value that can be obtained by using only the vertices in $V^{'}$ and disjoint elements from $S$ as $\begin{matrix} (5) & F (j, V^{'}) = max {\sum_{i \in I} ω (S_{i}) | I \subseteq {1, \dots, j}, j ⩽ | S | and I is feasible for V^{'}} . \end{matrix}$ Accordingly, we define $J (j, V^{'})$ as the index set that corresponds to the subsets that are chosen to obtain $F (j, V^{'})$ . Note that the definition of F implies that $F (| S |, V)$ contains the value of an optimal solution to the KEP and $J (| S |, V)$ the indices of the corresponding subsets.

The goal of the protocol $π_{KEP - DP}$ is then to determine the value $F (| S |, V)$ and the corresponding set of subsets indices $J (| P |, V)$ . We compute these by computing F and J for all $j \in {1, \dots, | S |}$ and for all $V^{'} \subseteq V$ in an iterative fashion. To this end, we rely on the recurrence stated in Theorem 15.

Theorem 15.
For all $j \in {1, \dots, | S |}$ and $V^{'} \in V$ , it holds that $\begin{matrix} (6) & \begin{aligned} F (0, V^{'}) = & 0, and \\ F (j, V^{'}) = & \{\begin{array}{ll} max {F (j - 1, V^{'}), F (j - 1, V^{'} ∖ S_{j}) + ω (S_{i})}, & if S_{j} \subseteq V^{'} \\ F (j - 1, V^{'}), & if S_{j} ⊈ V^{'} . \end{array} \end{aligned} \end{matrix}$
Proof.
The first equation follows from the definition of F.

For the second equation, let us first consider the case where $S_{j} ⊈ V^{'}$ . If the current subset $S_{j}$ is not in $V^{'}$ , then it holds that every index set $I \in {1, \dots, j}$ that is feasible for $V^{'}$ also satisfies $I \subseteq {1, \dots, j - 1}$ . Thus, $F (j - 1, V^{'}) = F (j, V^{'})$ .

For the case $S_{j} \subseteq V^{'}$ , we consider the two sets $I_{1} : = J (j - 1, V^{'})$ and $I_{2} : = J (j - 1, V^{'} ∖ S_{j})$ . We know that $I_{1}$ and $I_{2} \cup {j}$ are both feasible for $V^{'}$ . Thus, it follows that $\begin{aligned} F (j, V^{'}) & ⩾ max {ω (I_{1}), ω (I_{2} \cup {j}))} \\ = max {F (j - 1, V^{'}), F (j - 1, V^{'} ∖ S_{j}) + ω (S_{j})} . \end{aligned}$

For the other direction, assume some index set I is feasible for $V^{'}$ . Recall that by definition of J, it holds that $I_{1}$ indicates the subsets chosen for $F (j - 1, V^{'})$ and $I_{2}$ those for $F (j - 1, V^{'} ∖ S_{j})$ . Thus, if $j \notin I$ , then $ω (I) ⩽ ω (I_{1})$ and if $j \in I$ , then $ω (I ∖ {j} ⩽ ω (I_{2})$ . It follows that $\begin{aligned} F (j, V^{'}) & ⩽ max {ω (I_{1}), ω (I_{2} \cup {j}))} \\ = max {F (j - 1, V^{'}), F (j - 1, V^{'} ∖ S_{j}) + ω (S_{j})} . \end{aligned}$ □

Theorem 15 states that $F (j, V^{'})$ only depends on the values for $F (j - 1, V^{'})$ and $F (j - 1, V^{'} ∖ S_{j})$ . This allows us to compute $F (j, V^{'})$ for all $j \in {1, \dots, | S |}$ and $V^{'} \subseteq V$ in an iterative fashion such that at the end we obtain $F (| S |, V)$ and $J (| S |, V)$ , i.e., we obtain an optimal solution to the KEP.

Since the dynamic programming approach builds the set of optimal exchange cycles in an incremental fashion and only updates the currently known best solution if a new solution is strictly better, it prioritizes small cycles compared to larger cycles. Therefore, the ideal functionality for this approach has to be defined such that it provides for unbiasedness in the sense that given two patient-donor pairs $P_{i}$ and $P_{j}$ with identical input quotes, they have the same probability of being part of en exchange cycle in the computed solution. Note that this is sufficient for the use case of kidney exchange as unbiasedness between the different patient-donor pairs is required and not unbiasedness between all possible exchange constellations. Even further, short cycles are generally preferred as they have a smaller probability of failure compared to larger cycles (since less patient-donor pairs are involved, it is less likely that a transplant can not be carried out) [10].

Functionality 6 contains the definition of the ideal functionality $F_{KEP - DP}$ that is implemented by our privacy-preserving protocol $π_{KEP - DP}$ for solving the KEP using dynamic programming.
Functionality 6 ( $F_{KEP - DP}$ – Solving the KEP based on Dynamic Programming).

Let all computing peers hold the respective shares of the secret quotes $[Q_{i}]$ containing the medical data of the patient-donor pairs $P_{i}$ ( $i \in P$ ) as defined in Functionality 1 and Functionality 3 . Then, functionality $F_{KEP - DP}$ is given as $\begin{matrix} (([d_{1}], [r_{1}]), \dots, ([d_{| P |}], [r_{| P |}])) \leftarrow F_{KEP - DP} ([Q_{1}], \dots, [Q_{| P |}]), \end{matrix}$ where $(d_{i}, r_{i})$ are the indices of the computed donor and recipient for patient-donor pair $P_{i}$ for a set of exchange cycles that maximize the overall weight of the transplants for the pairs $P_{i}$ ( $i \in P$ ). If there are multiple solutions that yield the same maximum weight, one of those with the largest number of cycles of size 2 is chosen uniformly at random.

5.3.2. Protocol specification

Protocol 3 contains the specification of our protocol $π_{KEP - DP}$ for solving the KEP based on dynamic programming. The protocol is divided into four phases which are described in detail in the following. As in the protocol $π_{KEP - IP}$ (cf. Protocol 2), prior to the actual protocol execution each patient-donor pair $P_{i}$ ( $i \in P$ ) sends shares of the relevant medical data of its patient and donor to the computing peers. After the protocol execution, the computing peers then provide each patient-donor pair $P_{i}$ ( $i \in P$ ) with the shares of their computed exchange partners (indicated by $D (i)$ and $R (i)$ ).

Construction phase. This phase is the same as for protocol $π_{KEP - IP}$ since both protocols require the computation of the initial tableau for the subset formulation, which requires the matrices $A^{'}$ and $W^{'}$ as input. As in the protocol $π_{KEP - IP}$ , the shuffling ensures unbiasedness in the sense that two pairs with the same input have the same chance of being part of the computed solution (independent of their index).

Protocol 3

$π_{KEP - DP}$

Setup phase. The main purpose of the setup phase is to initialize all data structures that are required for solving the KEP based on dynamic programming. First, the gate $ρ_{IP - SETUP}$ is called to compute the tableau of the IP for the subset formulation (cf. Definition 7). Recall that the first row in this tableau $[T]$ stores the weight of each subset if it is executable under the current compatibility graph, and $[T] (1, i) = [0]$ , otherwise. The mapping $[M]$ then encodes the cycle for each subset. Afterwards, the matrices $[F]$ , $[J]$ , and $[I]$ are initialized. An entry $[F] (j, V^{'})$ with $j \in {1, \dots, | S |}$ and $V^{'} \subseteq V$ encodes the maximum value that can be obtained by using only the vertices in the vertex subset $V^{'}$ and disjoint sets from ${S_{1}, \dots, S_{j}}$ . The corresponding entry $[J] (j, V^{'})$ then contains the indices of those subsets that are chosen to obtain the value $[F] (j, V^{'})$ . As we start with the empty list of subsets (i.e., $j = 0$ ), the values of the first row of $[F]$ and $[J]$ are initially set to 0. An entry $[I] (j, V^{'})$ indicates the number of subsets that are part of the solution $[J] (j, V^{'})$ . We use the matrix $[I]$ to determine at which position the index of a new set has to be inserted into the set $[J] (j, V^{'})$ , i.e., the matrix $[I]$ encodes the next free entry in the list that is stored in $[J] (j, V^{'})$ .

Optimization phase. The general idea of this phase is to repeatedly construct an optimal set of exchange cycles by solving the KEP for all possible sets $V^{'} \subseteq V$ of patient-donor pairs and for all possible subsets $S$ of the subset formulation. In each iteration we solve the KEP for the subset $S_{i} \in S$ and the node set $V^{'} \subseteq V$ starting with $S_{1}$ and $V^{'} = {P_{1}}$ . To this end, we implement the recurrence from Theorem 15. If the new subset $S_{i}$ is not a subset of the current node set $V^{'}$ , then we copy all values from iteration $(i - 1, V^{'})$ as $S_{i}$ can only be part of the solution if all its nodes are in $V^{'}$ . If $S_{i}$ is a subset of $V^{'}$ , the entry $[F] (i, V^{'})$ is computed as the maximum of the solution without choosing $S_{i}$ (i.e., $F (i - 1, V^{'})$ ) and the solution that includes subset $S_{i}$ . In the latter case, we ensure that all chosen subsets are vertex disjoint by considering the solution that excludes all nodes from $S_{i}$ (i.e., $[F] (i - 1, V^{'} ∖ S_{i})$ ) and adding the weight of $S_{i}$ (i.e., $ω (S_{i}) = T (1, i)$ ). Similarly, we compute the set $[U]$ as the chosen subsets $[J] (i - 1, V^{'} ∖ S_{i}) \cup {i}$ . The matrix $[I]$ is used to store the number of subsets that have already been chosen for each solution. This is necessary to be able to determine the index $[I] (i - 1, V^{'} ∖ S_{i})$ at which a subset is inserted into the updated solution. In the last iteration, we then obtain a solution for the complete node set V and all subsets in $S$ . This corresponds to an optimal solution for the KEP. Afterwards, we transform the computed optimal set of subsets $[J] (| S |, P)$ into the solution vector $[X^{*}]$ where entry $[X^{*}] (i)$ indicates that subset $S_{i}$ is part of the found optimal solution.

Resolution phase. This phase is the same as for the protocol $π_{KEP - IP}$ .

Correctness. In order to show the correctness of protocol $π_{KEP - DP}$ , we have to show that the exchange partners that are computed by protocol $π_{KEP - DP}$ correspond to a set of exchange cycles that maximize the overall weight of the included transplants, chosen uniformly at random from all solutions of maximum weight that include the maximum possible number of exchange cycles of size 2.

Since protocol $π_{KEP - DP}$ implements the recurrence defined in Theorem 15, we know that the computed set of exchange cycles corresponds to the set encoded by $F (| S |, V)$ , which corresponds to a set of exchange cycles of maximum weight considering all elements from $S$ and all patient-donor pairs from $V : = P$ . Furthermore, the protocol $π_{KEP - DP}$ builds the solution set in an incremental fashion, adding new cycles iff the new solution set yields a strictly larger weight. Since $S$ is ordered such that it contains all subsets of size 2 followed by all subsets of size 3, the computed solution is guaranteed to contain the maximum possible number of cycles of size 2 among all solutions of maximum weight. It remains to show that the computed solution is chosen uniformly at random from all possible solutions of maximum weight containing the maximum possible number of cycles of size 2. This holds since the matrices $[A]$ and $[W]$ are shuffled uniformly at random previous to the computation of the initial tableau $[T]$ . This implies that the order of all subsets of size 2 is also chosen uniformly at random from all possible orders of these subsets. The same holds for the subsets of size 3.

Thus, protocol $π_{KEP - DP}$ correctly implements functionality $F_{KEP - DP}$ .

Theorem 16.

Protocol $π_{KEP - DP}$ (cf. Protocol 3 ) securely implements functionality $F_{KEP - DP}$ (cf. Functionality 6 ).

Proof (sketch).

The construction phase is simulated as for protocol $π_{KEP - IP}$ (cf. Theorem 14).

At the beginning of the setup phase, $S$ sets $⟨ [T] ⟩ \leftarrow_{$} Z_{M}^{(| P | + 1) \times (| S | + | P | + 1)}$ and $⟨ [M] ⟩ \leftarrow_{$} Z_{M}^{| S | \times λ_{max}}$ . Then, $S$ calls the simulator of gate $ρ_{IP - SETUP}$ on input $⟨ [A^{'}] ⟩$ , $⟨ [W^{'}] ⟩$ and output $⟨ [T] ⟩$ , $⟨ [M] ⟩$ . For the remainder of the setup phase, $S$ just follows the steps specified in Protocol 3.

In order to simulate the first steps of the optimization phase (Steps 21–24), $S$ follows the corresponding steps of Protocol 3 using the previously simulated values $⟨ [F] ⟩$ , $⟨ [T] ⟩$ , $⟨ [J] ⟩$ , and $⟨ [I] ⟩$ . For the computation of $⟨ [u] ⟩$ , $S$ calls the simulator of the comparison gate on input $⟨ [f^{1}] ⟩$ , $⟨ [F] (j - 1, V^{'}) ⟩$ and output $⟨ [u] ⟩ \leftarrow_{$} Z_{M}$ . For each of the following three calls to the selection gate, $S$ calls the corresponding simulator using the previously simulated values as input and random shares from $Z_{M}$ as output. To simulate Steps $30 - 32$ , $S$ then again just follows the specification of Protocol 2, using the previously simulated values $⟨ [F] ⟩$ , $⟨ [I] ⟩$ , and $⟨ [J] ⟩$ . At the end of the optimization phase, $S$ calls the simulator of gate $ρ_{{DEMUX}^{| S |}}$ on input $⟨ [J] (| S |, | P |, i) ⟩$ and output $⟨ [ind] (i) ⟩ \leftarrow_{$} Z_{M}^{| S |}$ for $i \in {0, \dots, ⌊ | P | / 2 ⌋ - 1}$ . The computation of $⟨ [X^{*}] ⟩$ is then simulated by computing the sum over all simulated values $⟨ [ind] (i) ⟩$ for $i \in {0, \dots, ⌊ | P | / 2 ⌋ - 1}$ as specified in Protocol 3.

The resolution phase is simulated as for protocol $π_{KEP - IP}$ (cf. Theorem 14).

Since all gates that are called during the execution of $π_{KEP - DP}$ have already been shown to be secure in the semi-honest security model and due to the properties of the underlying secret sharing scheme, $S$ creates a view that is statistically indistinguishable from ${VIEW}_{I_{C}}^{π}$ . □

5.3.3. Complexity analysis

Communication and round complexity of protocol $π_{KEP - DP}$ are dominated by the optimization phase. The $| S | \cdot 2^{| P |}$ iterations all depend on each other and thus cannot be executed in parallel. Each iteration itself is dominated by the call to the comparison gate. This yields the overall communication complexity $O (| S | \cdot 2^{| P |} \cdot s)$ and round complexity $O (| S | \cdot 2^{| P |})$ .

5.3.4. Extension for exchange chains

Since all changes that have to be applied to the protocol $π_{KEP - DP}$ in order to obtain a protocol $π_{KEP - DP - CC}$ that also includes altruistic donors and exchange chains concern the construction of the initial tableau T and the resolution of the exchange partners based on the computed solution vector $X^{*}$ and the secret mapping $M$ , we have to apply exactly the same changes to construction, setup, and resolution phase as for the protocol $π_{KEP - IP}$ (cf. Section 5.2.4). All other phases of the protocol $π_{KEP - DP - CC}$ are exactly the same as in protocol $π_{KEP - DP}$ .

6. Evaluation

We evaluate run time and network traffic for all three protocols $π_{KEP - RND}$ , $π_{KEP - IP}$ , and $π_{KEP - DP}$ as well as for the extended versions that also consider exchange chains. Thereby, we are able to determine the impact of prioritization and exchange chains on the performance of these protocols.

Table 3
Criteria for the prioritization function that is used throughout the evaluation. The criteria are derived from the information on the patient-donor pairs that is included in our real-world data set from UNOS

Category Criteria

Pre-score – Blood type of patient and donor

– Calculated panel reactive antibody (CPRA) a

– Waiting time

– Pediatric patient

– Prior living donor

Equality criteria – Common HLA of patient and donor

– Same blood type for patient and donor

Difference criteria – Age difference between patient and donor

– Age difference between donor and donor

Travel distance – Region of patient and donor

Category	Criteria
Pre-score	– Blood type of patient and donor
– Calculated panel reactive antibody (CPRA) a
– Waiting time
– Pediatric patient
– Prior living donor
Equality criteria	– Common HLA of patient and donor
– Same blood type for patient and donor
Difference criteria	– Age difference between patient and donor
– Age difference between donor and donor
Travel distance	– Region of patient and donor

The CPRA states the probability that any donor is compatible with the patient based on the distribution of HLA among the society [34].

6.1. Evaluation setup

We implemented our protocols in the SMPC benchmarking framework MP-SPDZ [28] version 0.3.5.4

⁴
https://github.com/data61/MP-SPDZ/releases/tag/v0.3.5

We fix the number of computing peers to three which is the most commonly considered setup (e.g., [11,12]). We use the secret-sharing scheme by Araki et al. [4] which to the best of our knowledge is the most efficient scheme in the semi-honest model with honest majority and three computing peers.

Network setup. We model each computing peer as a separate container on a single server with an AMD EPYC 7702P 64-core processor. Each container runs Ubuntu 20.04 LTS, has a single core, and 32 GB RAM. The input peers are modeled by a fourth container with the same specifications. In order to provide for a realistic network setup, we follow Breuer et al. [14,16] and consider a latency of 1ms and a bandwidth of 1Gbps between the computing peers.

Data set. We use a data set from the United Network for Organ Sharing (UNOS) for the input of the patient-donor pairs.5

⁵

The data reported here have been supplied by the United Network for Organ Sharing as the contractor for the Organ Procurement and Transplantation Network. The interpretation and reporting of these data are the responsibility of the author(s) and in no way should be seen as an official policy of or interpretation by the OPTN or the U.S. Government.

The data set contains all patient-donor pairs and altruists that registered at UNOS between 27th October 2010 and 29th December 2020 resulting in 2913 unique patient-donor pairs and 113 altruistic donors. For each protocol run, we sample from the set of all unique pairs and altruists uniformly at random. For our compatibility check gate

ρ_{COMP - CHECK}

(cf. Section 3.2), we consider all HLA that have been reported for the patient-donor pairs and altruists in the data set. This is a total of 348 antigens across the six loci A, B, C, DR, DQ, and DP.

Prioritization function. While in Section 4 we provide a general gate for prioritization, in our evaluations we have to decide on a specific prioritization function to be implemented. This is not trivial as different platforms for kidney exchange consider very different criteria for prioritization [7,10]. In particular, there is not one prioritization function that can be considered supreme to all others. Therefore, we decide to use a prioritization function that considers all criteria that can be derived from our real-world data set from UNOS. This has the advantage that we use realistic values for the input of the patient-donor pairs and altruists. Table 3 shows the different criteria that we derive from our real-world data set together with their corresponding categories as defined in Section 4.1.

Table 4

Parameters and their values for the evaluation of the protocols $π_{KEP - RND}$ , $π_{KEP - IP}$ , and $π_{KEP - DP}$

Parameter	Values
Number of computing peers	3
Secret-sharing scheme	Araki et al. [4]
Latency	1 ms
Bandwidth	1 Gbps
Maximum cycle size λ	3
Maximum chain length κ	3, 4
Number of repetitions	$π_{KEP - RND}$ and $π_{KEP - DP}$	10 if run time ⩽1h
	$π_{KEP - RND}$ and $π_{KEP - DP}$	1 if run time >1h
	$π_{KEP - IP}$	50

Evaluation parameters. We evaluate all protocols for increasing numbers of patient-donor pairs for the setting with exchange cycles only and also their extended versions that allow for exchange cycles and chains. We use a maximum cycle size $λ = 3$ and for the chain length κ, we consider values 3 and 4 since these are the most common values used in existing kidney exchange platforms [7,10].

With respect to the number of repetitions per measurement, we distinguish between the two protocols $π_{KEP - RND}$ and $π_{KEP - DP}$ on the one side and protocol $π_{KEP - IP}$ on the other side. The former two protocols are data-oblivious, i.e., their flow of execution and thereby also their run time are independent of the input. Thus, for these two protocols a small number of repetitions per number of patient-donor pairs is sufficient. In particular, we execute each measurement 10 times for run times up to 1 hour and once for run times longer than 1 hour. For the protocol $π_{KEP - IP}$ this is, however, not sufficient since the run times of the Simplex algorithm and the Branch-and-Bound algorithm vary for different inputs. Therefore, we run 50 repetitions with different inputs of the patient-donor pairs for each measurement. As we use real-world data for the input of the pairs, the run times that we obtain for the protocol $π_{KEP - IP}$ are representative for a real-world kidney exchange setting. Note that we use a step size of 5 for more than 20 patient-donor pairs due to the high number of repetitions for the protocol $π_{KEP - IP}$ and the associated long run times of the measurements. We then provide the average of run time and network traffic for all repetitions of a measurement. Table 4 summarizes the parameters considered in our evaluation.

For each measurement, we determine the run time and the induced network traffic. A measurement starts when the computing peers have received the input of all participating patient-donor pairs and it ends when the computing peers have sent the output back to the pairs. The network traffic is defined as the overall data sent by the three computing peers during the protocol execution. For the two protocols $π_{KEP - RND}$ and $π_{KEP - DP}$ , we aborted a measurement if it exceeded a run time of 24 hours or if a computing peer required more than 32 GB RAM. Since we execute 50 repetitions per measurement for the protocol $π_{KEP - IP}$ , we aborted a measurement for this protocol if it exceeded an average run time of 2 hours.

6.2. Results for exchange cycles only

Figure 2 contains plots for run times and network traffic for the protocols $π_{KEP - RND}$ , $π_{KEP - IP}$ , and $π_{KEP - DP}$ when considering exchange cycles only with maximum cycle size $λ = 3$ . Note that the y-axis has a logarithmic scale. The exact values can be found in Table 5 (Appendix A).

We observe that the protocol $π_{KEP - RND}$ exhibits the lowest run times for up to 7 patient-donor pairs. However, for larger numbers of pairs the other protocols significantly outperform the protocol $π_{KEP - RND}$ . This is due to its brute force nature, i.e., the protocol scales with the size of the set of exchange constellation graphs $G^{EC}$ which increases exponentially with the number of patient-donor pairs. While the protocol $π_{KEP - DP}$ also exhaustively searches the solution space for the KEP it scales with $| S | \cdot 2^{| P |}$ which grows slower than the set $G^{EC}$ .

While protocol $π_{KEP - DP}$ outperforms protocol $π_{KEP - RND}$ for more than 9 patient-donor pairs, its run time also increases exponentially and thus for 16 pairs it already exceeds 24 hours. This exponential increase of the run time of both the protocols $π_{KEP - RND}$ and $π_{KEP - DP}$ is due to the NP-completeness of the KEP for cycle size restrictions larger than 2.

Fig. 2.

Run times and network traffic for the three protocols $π_{KEP - RND}$ , $π_{KEP - IP}$ , and $π_{KEP - DP}$ for exchange cycles of maximum size $λ = 3$ for increasing numbers of patient-donor pairs. The scale of the y-axis is logarithmic.

In contrast to the brute force nature of these two protocols, the protocol $π_{KEP - IP}$ follows a different approach in that it is based on the Simplex algorithm and the Branch-and-Bound algorithm which repeatedly prune the search space and thereby achieve a sub-exponential run time on average. The results in Table 5 confirm this in that the protocol $π_{KEP - IP}$ significantly outperforms the two other protocols for numbers of patient-donor pairs larger than 7. For smaller numbers of pairs, the overhead of the gate for the Simplex algorithm is larger compared to the small size of the search space that has to be searched by the brute force approaches. This is in line with the general result that the Simplex algorithm on average scales sub-exponentially for most practical use cases [35].

Furthermore, we observe that the plot for Protocol $π_{KEP - IP}$ is not smooth. This is due to the fact that the protocol is not data oblivious. In particular, the number of iterations that the Simplex algorithm requires and the structure of the Branch-and-Bound tree are not deterministic for a fixed number of patient-donor pairs. Note that the performance of the Simplex algorithm is mostly determined by the number of constraints, variables, and non-zero entries of the underlying tableau [32].

Fig. 3.

Run time consumption of the different phases of the protocols $π_{KEP - RND}$ , $π_{KEP - IP}$ , and $π_{KEP - DP}$ for increasing numbers of patient-donor pairs. Note that construction and prioritization phase are the same for all protocols. For the two protocols $π_{KEP - IP}$ and $π_{KEP - DP}$ also the shuffling, IP setup, and resolution phases are identical. All other phases are different for the three protocols.

6.3. Impact of prioritization

In Section 4, we introduced our generic prioritization gate which we further specified for our evaluation in Table 3. We now evaluate the impact of the inclusion of prioritization on the run time performance of each of the three protocols.

Figure 3 shows the run time consumption of the different phases of each protocol. In order to show the impact of prioritization, we divide the first phase of all protocols into a construction phase (computation of the adjacency matrix A) and a prioritization phase (computation of the prioritization matrix W). For the protocol $π_{KEP - RND}$ , we also consider the computation of the weight of each exchange constellation (Protocol 1, Step 7) as part of the prioritization phase. We observe that for 3 patient-donor pairs the percentage of the run time that is consumed by the prioritization phase is larger than $50 %$ for the protocols $π_{KEP - RND}$ and $π_{KEP - DP}$ and about $46 %$ for the protocol $π_{KEP - IP}$ . However, with an increasing number of patient-donor pairs this percentage decreases rapidly for all three protocols. For 8 pairs, the percentage of run time consumed by the prioritization phase is below $10 %$ for protocol $π_{KEP - RND}$ . This percentage further decreases to less than $5 %$ for 12 pairs. For the protocol $π_{KEP - IP}$ the prioritization phase consumes less than $10 %$ of the overall run time from 15 pairs on and even less than $1 %$ from 35 pairs on. The prioritization phase has the smallest impact on the protocol $π_{KEP - DP}$ , consuming less than $1 %$ of the overall run time from 8 pairs on. Note that this small impact of the prioritization phase on all three protocols holds even for a prioritization function that considers as many criteria as the one indicated in Table 3. Further increasing the number of criteria in the prioritization function would not significantly change this behavior since the run time of all three protocols is clearly dominated by the computation of the optimal set of exchange cycles, i.e., by the evaluation, mapping, and selection phases for protocol $π_{KEP - RND}$ and by the optimization phase for the protocols $π_{KEP - DP}$ and $π_{KEP - IP}$ .

However, note that, in contrast to the protocols $π_{KEP - RND}$ and $π_{KEP - DP}$ , for the protocol $π_{KEP - IP}$ the prioritization function also influences the run time of the optimization phase. This is due to the inner workings of the Simplex protocol, which repeatedly tries to improve the solution by adding another subset until an optimal solution is found. Consider the example of two subsets of the same size that share a node. Only one of them can be part of the optimal solution. In the case without prioritization, both subsets have the same weight and thus it does not matter which of them is chosen. With prioritization, however, the two subsets are likely to have different weights. If the Simplex protocol now adds the subset of lower weight first, then it has to substitute it with the subset of larger weight in a subsequent iteration. This intuitively explains why the protocol $π_{KEP - IP}$ requires significantly more Simplex iterations on average if prioritization is used. Since the run time of the protocol is heavily influenced by the number of Simplex iterations, this also explains the significantly increased run times for the setting with prioritization. In particular, the optimization phase on average takes about 1.33 times longer with prioritization than reported in [15] for the setting without prioritization. This factor increases with the number of patient-donor pairs since the compatibility graph contains more cycles for larger numbers of pairs. For example, for 35 pairs the protocol with prioritization takes about 1.91 times longer than without prioritization.

Fig. 4.

Run times for the protocols $π_{KEP - RND - CC}$ , $π_{KEP - IP - CC}$ , and $π_{KEP - IP - CC}$ for cycles of maximum size $λ = 3$ and different values for the maximum chain length κ. Note that a maximum chain length $κ = ⊥$ indicates that chains are not considered, I.e., these are results for the protocols when only cycles are allowed. The scale of the y-axis is logarithmic.

6.4. Results for exchange cycles and exchange chains

Figure 4 shows the run times for the protocols without chains, with maximum chain length $κ = 3$ , and with $κ = 4$ . The corresponding values can be found in Table 6, Appendix A. As expected, the run time increases for all three protocols with an increasing maximum chain length. However, the impact of the inclusion of exchange chains is much larger for the protocol $π_{KEP - RND}$ than for the two protocols $π_{KEP - IP}$ and $π_{KEP - DP}$ . The heavy increase for protocol $π_{KEP - RND}$ is due to the increased size of the set of exchange constellations $G^{EC}$ for exchange chains (cf. Table 2). The other two protocols benefit from the use of the subset formulation (cf. Definition 7). Note that the size of the IP that has to be solved does not increase at all if in addition to exchange cycles also chains of length 3 are included. Only the construction of the initial tableau for the subset formulation and the resolution from the chosen subsets to the actual exchange partners are impacted by the inclusion of chains of length 3. These, however, have a comparatively small impact on the run time. For exchange chains of length 4, the impact is considerably larger since the number of variables in the IP increases as also all subsets of size 4 have to evaluated. However, even for chains of length 4 the impact on the run time is much smaller for the protocols that use the subset formulation than for the protocol $π_{KEP - RND}$ .

6.5. Discussion

Overall, our evaluations show that the run time of all three protocols increases significantly for increasing numbers of patient-donor pairs. While the protocol $π_{KEP - IP}$ is the most efficient one, it also already requires about 1.5 hours for 35 patient-donor pairs in the setting with cycles only. This is sufficient for small countries, where only few patient-donor pairs participate in the platform. However, for large platforms such as UNOS in the United States, it is necessary to solve the KEP for more than 200 patient-donor pairs at once. One possibility to nevertheless use privacy-preserving kidney exchange in such platforms is to split the large pool of patient-donor pairs into several smaller sub-pools for which the protocols still exhibit feasible run times. In that case it is necessary to determine the impact of the pool splitting on the number of transplants that can be found. Breuer et al. [16] already showed that this impact is small for the special case of crossover kidney exchange (i.e., exchange cycles of size 2). However, the evaluation of our protocols in such a dynamic setting where pairs arrive and leave over time is beyond the scope of this work.

7. Related work

There are two main areas of research that are related to our work. First, the different existing non-privacy-preserving platforms for kidney exchange and their way of modeling kidney exchange. Second, other privacy-preserving approaches in the context of kidney exchange.

7.1. Conventional kidney exchange

The goal of this work is to develop SMPC protocols for kidney exchange that achieve the same properties as the algorithms deployed by existing non-privacy-preserving kidney exchange platforms. There are three main aspects in which the existing platforms differ among each other: The algorithmic approaches, the restriction on the length of cycles and chains, and the criteria that are used for prioritization.

Algorithmic approaches. Those platforms that only allow for cycles of size 2, typically use Edmonds’ algorithm [24] or some variation of it [7,10]. However, since we consider the more general case where the cycle size is restricted to $λ ⩾ 3$ , we cannot use a protocol based on Edmonds’ algorithm.6

⁶
Note that the SMPC protocol from [16] already provides an efficient privacy-preserving solution for the special case of exchange cycles of size 2.

If also longer cycles and chains are allowed, the state-of-the-art approach is to solve an IP formulation of the KEP [7,10]. There are two main IP formulations of the KEP in conventional platforms, i.e., the edge formulation and the cycle formulation [1]. The former introduces one variable for each edge and the latter one variable for each cycle or chain in the compatibility graph. It has been shown that the cycle formulation in general requires less constraints than the edge formulation when restricting the maximum cycle size or chain length to a value larger or equal to 3 [1]. In order to solve the IP formulations of the KEP a variety of optimization methods and adapted formulations have been proposed (e.g., [2,23,26,31]). However, there is not a single method that is followed by all platforms. Instead, each platform typically uses its own method for solving the KEP targeted to its particular characteristics such as the size of the population that it serves or the particular prioritization criteria that are considered [7,10]. Our protocol $π_{KEP - IP}$ (cf. Section 2) follows an IP approach by using the subset formulation (cf. Definition 7), which is based on the cycle formulation. Our evaluations show that, similar to the results for the non-privacy-preserving setting, the IP based approach also is the most efficient approach in the privacy-preserving setting (cf. Section 6.2).

Restrictions on cycle and chain lengths. Most platforms specify an upper bound of 3 on the maximum allowed length of an exchange cycle. This includes the national platforms in the Netherlands, Spain, Portugal, the UK, Australia, and France as well as the Alliance for Paired Kidney Donation (APKD), the National Kidney Registry (NKR), and UNOS in the United States [7,10]. In contrast to this, exchange chains are not considered at all in many platforms as the corresponding countries do not allow for the altruistic donation of kidneys. This includes France, Belgium, Austria, Sweden, Switzerland, Poland, and Greece [7]. Most platforms that do consider exchange chains usually restrict their length to 3 (e.g., United Kingdom) or 4 (e.g., the Netherlands, UNOS) [7,10].

Since all our protocols allow for the arbitrary restriction of the maximum cycle and chain lengths, they can be used for any of these settings. However, our evaluations show that the run times of all three protocols become infeasible for large numbers of patient-donor pairs. Therefore, our protocols can only directly be applied in countries where the number of patient-donor pairs is not too large. A possible solution for countries with larger numbers of pairs is to split the pairs into multiple small pools for which our protocols still exhibit feasible run times.

Criteria for prioritization. Most platforms consider the maximization of the overall number of found transplants as the most important criterion. This means that they first maximize the size of the solution and then use the other criteria only to break ties. Countries whose nationwide platforms follow this pattern include Belgium, Czech Republic, Netherlands, Poland, Portugal, Spain, and Sweden [10]. Further prioritization criteria that are considered by many platforms are so-called hard-to-match patients (i.e., patients who are less likely to be included in a match due to their medical characteristics), patients who are already on dialysis for a long time, or transplants between the same blood group [7,10]. However, the criteria that are considered and also their weight differ considerably among the existing platforms.

Therefore, we devise a generic gate for prioritization that can be used to realize a wide range of different prioritization functions (cf. Section 4). In particular, we specify different categories for the criteria and show how these can be implemented using SMPC. This makes our gate flexible such that each platform that wants to use our protocols can decide individually on its own prioritization function.

7.2. Privacy-preserving kidney exchange

To the best of our knowledge, there are only two lines of work in the area of privacy-preserving kidney exchange, i.e., the SMPC protocols for solving the KEP by Breuer et al. [14,16,17] and the approximation protocol by Birka et al. [8].

Breuer et al. [16] present an SMPC protocol for the special case of crossover exchange (i.e., exchange cycles of size 2) based on a privacy-preserving implementation of a maximum matching algorithm. They also consider the setup where patient-donor pairs distribute their medical input among a set of computing peers who then execute the actual SMPC protocol. The major difference to the three protocols presented in this paper is that their protocol is only able to detect cycles of size 2 whereas the three presented protocols can be used for any restriction of the maximum cycle size. Besides, the protocols presented in this work are also capable of prioritizing certain patient-donor pairs and detecting exchange chains.

In the same line of work, Breuer et al. [14,17] present the two SMPC protocols $π_{KEP - RND}$ and $π_{KEP - IP}$ for solving the KEP for any restriction on the maximum cycle size. While these protocols solve this more general setting of the KEP, they fail to address some requirements for solving the KEP in practice. In particular, they neither allow for prioritization (i.e., they only consider the unweighted KEP) nor for the inclusion of altruistic donors and exchange chains. In Section 5.1 and Section 5.2, we close these gaps by extended the two existing protocols $π_{KEP - RND}$ and $π_{KEP - IP}$ accordingly. Since the protocol $π_{KEP - RND}$ [17] is only efficient for very small numbers of patient-donor pairs and the protocol $π_{KEP - IP}$ [14] is not entirely data oblivious, we propose one additional SMPC protocol for solving the KEP with prioritization and exchange chains (cf. Section 5.3). This protocol is more efficient than the protocol $π_{KEP - RND}$ and it is data oblivious. However, it is not as efficient as the protocol $π_{KEP - IP}$ .

Birka et al. [8] present another SMPC protocol in the context of kidney exchange. In contrast to the existing privacy-preserving protocols for kidney exchange [14,16,17] and also the algorithms used by existing non-privacy-preserving kidney exchange platforms [7,10], the protocol proposed in [8] does not compute an exact solution to the KEP. Instead, it computes some (non-optimal) set of possible exchange cycles for a single fixed cycle size λ. This set of cycles only forms an approximate solution to the KEP as it does not maximize the number of cycles for the fixed λ and it also does not consider all possible cycles of size less than λ. Thus, it solves a much easier problem which in comparison to the KEP is not NP-complete. While the run time of the protocol is evaluated in [8], the quality of the evaluation is not evaluated. However, the quality of the solution is of utmost importance for the use case of kidney exchange where any possible exchange that is not found may have severe consequences for the corresponding patients. This is further stressed by the fact that the maximization of the number of found transplants is the most important prioritization criterion in almost all existing platforms [10]. Besides this, the protocol from [8] is not data oblivious, i.e., it reveals the number of exchange cycles that exist in the otherwise private compatibility graph. It also does not allow for the detection of exchange chains which makes it unsuitable for countries where such chains are allowed. While the protocol from [8] does use prioritization, it only shows how some of the prioritization criteria that are considered by existing kidney exchange platforms could be implemented in a privacy-preserving fashion. In contrast to this, we specify different categories of criteria which cover the wide range of criteria that are considered by existing platforms. We then provide a generic prioritization gate that implements the different criteria and thus allows for the inclusion of any prioritization criteria. Thereby, we maximize the flexibility when it comes to deciding which criteria shall be included for prioritization and how they shall be weighted against each other.

8. Conclusion and future work

We have extended the only two existing SMPC protocols [14,17] for (optimally) solving the KEP for exchange cycles of size 3 or larger such that they support the entire functionality offered by current kidney exchange platforms. In particular, we specified how prioritization and exchange chains can be integrated into these privacy-preserving solutions. We also presented one novel protocol that solves the KEP with prioritization for cycles and chains. We have shown that our novel protocol outperforms the existing brute force approach. The best performance is achieved by the approach based on privacy-preserving integer programming which, however, is not entirely data oblivious in contrast to the other two protocols. The main results of our evaluation are that the impact of prioritization on the performance of the two data oblivious protocols is small except for small numbers of patient-donor pairs and that the inclusion of chains induces a comparatively huge performance impact for chains of size 4 or larger.

While our protocols achieve all properties that are required by existing platforms for kidney exchange, their run time becomes infeasible if too many patient-donor pairs are involved. Thus, an interesting direction for future work is the development of privacy-preserving solutions for platforms with large numbers of registered patient-donor pairs. A further potential direction for future research is to evaluate the performance of our SMPC protocols in a dynamic setting where pairs arrive and leave over time.

Source code

The MP-SPDZ source code of our protocols $π_{KEP - RND}$ , $π_{KEP - IP}$ , and $π_{KEP - DP}$ together with their extensions for altruistic donors and exchange chains and a script for executing the protocols on a sample set of randomly generated patient-donor pairs are available under the following link: https://gitlab.com/rwth-itsec/kep-prioritization-and-chains/.

While we cannot publish the inputs from our real-world data set, this data can be requested from UNOS by anyone who is interested.

Footnotes

Acknowledgments

This work was funded by the Deutsche Forschungsgemeinschaft (DFG, German Resarch Foundation) – project number (419340256) and NSF grant CCF-1646999. Any opinion, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Additional evaluation results

In this section, we present the values for run time and network traffic for all three protocols for exchange cycles only and for exchange chains of length 3 and 4.

Table 5 contains the results for exchange cycles only with maximum cycle size $λ = 3$ corresponding to the plots in Fig. 2. We essentially make the same observations for the network traffic as for the run time evaluation. In particular, the two brute force approaches $π_{KEP - RND}$ and $π_{KEP - DP}$ initially generate less traffic than the IP based approach of protocol $π_{KEP - IP}$ but from 7 patient-donor pairs on, the protocol $π_{KEP - IP}$ outperforms the other two protocols in terms of induced network traffic.

Table 6 contains the results for the protocols with exchange cycles and chains of length 3 and 4 corresponding to the plots in Fig. 4. Overall, the results show that the observations for the comparison between the protocols for cycles only also apply to the setting with cycles and chains. In particular, the protocol $π_{KEP - IP}$ also exhibits the best performance for the setting with cycles and chains, followed by the protocol $π_{KEP - DP}$ . The protocol with the worst performance is still the protocol $π_{KEP - RND}$ .

Protocols for exchange chains

In this section, we provide the detailed specifications of the gates and protocols that have to be modified significantly when considering exchange chains in addition to exchange cycles.

Gate 4 contains the specification of the gate $ρ_{IP - SETUP}$ (cf. Gate 2) when extended to exchange chains. The changes that are required to obtain Gate 4 from Gate 2 are stated in Section 3.3.

Protocol 4 contains the specification of the protocol $π_{KEP - RND - CC}$ which forms an extension of the protocol $π_{KEP - RND}$ (cf. Protocol 1). The changes that have to be applied to protocol $π_{KEP - RND}$ in order to obtain the protocol $π_{KEP - RND - CC}$ which is able to detect exchange chains and cycles are stated in Section 5.1.4.

Simulators

References

D.J.

Abraham,

Blum and

Sandholm, Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchange, ACM Conference on Electronic Commerce (2007), ACM.

Anderson,

Ashlagi,

Gamarnik and

A.E.

Roth, Finding long chains in kidney exchange using the traveling salesman problem, Proceedings of the National Academy of Sciences 112(3) (2015).

Andersson,

Biró,

Calderön,

Chromy,

A.N.

Costa,

Cozzi,

Delgado,

Dworczak,

Fiaschetti,

Garcia,

Haase-Kromwijk,

Hemke,

Klimentova,

Kuypers,

Lombardini,

Manlove,

Petterson,

Rais,

Santos,

Smeulders,

Sparacino,

Spieksma,

Valentín,

van de Klundert,

Vespasiano and

Viana, Modelling and optimisation in European kidney exchange programmes, 2019, https://www.enckep-cost.eu/assets/content/156/enckep_wg1_handbook2-20210407142449-156.pdf .

Araki,

Furukawa,

Lindell,

Nof and

Ohara, High-throughput semi-honest secure three-party computation with an honest majority, in: Computer and Communications Security, ACM, 2016.

Araki,

Furukawa,

Ohara,

Pinkas,

Rosemarin and

Tsuchida, Secure graph analysis at scale, in: Computer and Communications Security, ACM, 2021.

Ashlagi,

Bingaman,

Burq,

Manshadi,

Gamarnik,

Murphey,

A.E.

Roth,

M.L.

Melcher and

M.A.

Rees, Effect of match-run frequencies on the number of transplants and waiting times in kidney exchange, in: American Journal of Transplantation, Vol. 18, Wiley Online Library, 2018.

Ashlagi and

A.E.

Roth, Kidney exchange: an operations perspective, Technical Report, 9, 2021, INFORMS.

Birka,

Hamacher,

Kussel,

Möllering and

Schneider, SPIKE: Secure and private investigation of the kidney exchange problem, BMC Medical Informatics and Decision Making 22(253) (2022).

Biró,

Haase-Kromwijk,

Andersson,

E.I.

Ásgeirsson,

Baltesová,

Boletis,

Bolotinha,

Bond,

Böhmig,

Burnapp et al., Building kidney exchange programmes in Europe – An overview of exchange practice and activities, Transplantation 103(7) (2019).

10.

Biró,

van de Klundert,

Manlove,

Pettersson,

Andersson,

Burnapp,

Chromy,

Delgado,

Dworczak,

Haase et al., Modelling and optimisation in European kidney exchange programmes, in: European Journal of Operational Research, Elsevier, 2019.

11.

Bogdanov,

Jõemets,

Siim and

Vaht, How the Estonian tax and customs board evaluated a tax fraud detection system based on secure multi-party computation, in: Financial Cryptography and Data Security, Springer, 2015.

12.

Bogdanov,

Laur and

Willemson, Sharemind: A framework for fast privacy-preserving computations, in: European Symposium on Research in Computer Security, Springer, 2008.

13.

Bogetoft,

D.L.

Christensen,

Damgård,

Geisler,

Jakobsen,

Krøigaard,

J.D.

Nielsen,

J.B.

Nielsen,

Pagter et al., Secure multiparty computation goes live, in: International Conference on Financial Cryptography and Data Security, Springer, 2009.

14.

Breuer,

Hein,

Pompe,

Temme,

Meyer and

Wetzel, Solving the kidney exchange problem using privacy-preserving integer programming, in: Annual International Conference on Privacy, Security & Trust (PST), IEEE, 2022.

15.

Breuer,

Hein,

Pompe,

Temme,

Meyer and

Wetzel, Solving the kidney exchange problem using privacy-preserving integer programming (updated and extended version), 2023, arXiv preprint, https://arxiv.org/abs/2208.11319 arXiv:2208.11319.

16.

Breuer,

Meyer and

Wetzel, Privacy-preserving maximum matching on general graphs and its application to enable privacy-preserving kidney exchange, in: Conference on Data and Application Security and Privacy, ACM, 2022.

17.

Breuer,

Meyer,

Wetzel and

Mühlfeld, A privacy-preserving protocol for the kidney exchange problem, in: Workshop on Privacy in the Electronic Society, ACM, 2020.

18.

Canetti, Security and composition of multiparty cryptographic protocols, Journal of CRYPTOLOGY 13 (2000), 143–202. doi:10.1007/s001459910006.

19.

Catrina and

De Hoogh, Improved primitives for secure multiparty integer computation, in: International Conference on Security and Cryptography for Networks, Springer, 2010.

20.

Catrina and

S.d.

Hoogh, Secure multiparty linear programming using fixed-point arithmetic, in: European Symposium on Research in Computer Security, Springer, 2010.

21.

Damgård and

J.B.

Nielsen, Universally composable efficient multiparty computation from threshold homomorphic encryption, in: Annual International Cryptology Conference, Springer, 2003.

22.

Dantzig, Linear Programming and Extensions, Princeton University Press, 1963.

23.

J.P.

Dickerson,

A.D.

Procaccia and

Sandholm, Optimizing kidney exchange with transplant chains: Theory and reality, in: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems – Volume 2, 2012.

24.

Edmonds, Paths, trees, and flowers, Canadian Journal of Mathematics, 17 (1965), 449–467.

25.

Eurotransplant, Annual Report 2021, 2022. https://www.eurotransplant.org/wp-content/uploads/2022/06/Annual-Report-2021_LR.pdf.

26.

K.M.

Glorie,

J.J.

van de Klundert and

A.P.

Wagelmans, Kidney exchange with long chains: An efficient pricing algorithm for clearing barter exchanges with branch-and-price, Manufacturing & Service Operations Management 16(4) (2014).

27.

Goldreich, Foundations of Cryptography: Volume 2 – Basic Applications, Cambridge University Press, 2004.

28.

Keller, MP-SPDZ: A versatile framework for multi-party computation, in: Computer and Communications Security, ACM, 2020.

29.

A.H.

Land and

A.G.

Doig, An automatic method for solving discrete programming problems, Econometrica 28(3) (1960).

30.

Launchbury,

I.S.

Diatchki,

DuBuisson and

Adams-Moran, Efficient lookup-table protocol in secure multiparty computation, in: SIGPLAN International Conference on Functional Programming, ACM, 2012.

31.

D.F.

Manlove and

O’malley, Paired and altruistic kidney donation in the UK: Algorithms and experimentation, Journal of Experimental Algorithmics (JEA) 19 (2015).

32.

E.H.

McCall, Performance results of the simplex algorithm for a set of real-world linear programming models, Communications of the ACM 25(3) (1982), 207–212. doi:10.1145/358453.358461.

33.

A.J.

Miller,

B.A.

Kiberd,

I.P.

Alwayn,

Odutayo and

K.K.

Tennankore, Donor-recipient weight and sex mismatch and the risk of graft loss in renal transplantation, Clinical Journal of the American Society of Nephrology 12(4) (2017), 669–676. doi:10.2215/CJN.07660716.

34.

Organ Procurement and Transplantation Network, https://optn.transplant.hrsa.gov/media/eavh5bf3/optn_policies.pdf, Accessed 16-Nov-2022.

35.

Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, 1998.

36.

Shamir, How to share a secret, Communications of the ACM 22(11) (1979). doi:10.1145/359168.359176.

37.

Toft, Solving linear programs using multiparty computation, in: Financial Cryptography and Data Security, Springer, 2009.

38.

Waksman, A permutation network, in: Journal of the ACM, Vol. 15, ACM, 1968.

39.

World, Organization, https://www.who.int/news-room/fact-sheets/detail/the-top-10-causes-of-death, Top 10 Causes of Death, Accessed 23-Dec-2022.

40.

Wüller,

Meyer and

Wetzel, Towards privacy-preserving multi-party bartering, in: Financial Cryptography and Data Security, Springer, 2017.

41.

Zahur,

Wang,

Raykova,

Gascón,

Doerner,

Evans and

Katz, Revisiting square-root ORAM: Efficient random access in multi-party computation, in: IEEE Symposium on Security and Privacy, IEEE, 2016.

Prioritization and exchange chains in privacy-preserving kidney exchange

Abstract

Keywords

1. Introduction

1 Note that it is hard to develop an efficient data oblivious SMPC protocol for the KEP since the KEP is NP-complete for cycle size restrictions larger than 2 [1].

2.1. Graph theory

2.2. Secure multi-party computation

Definition 1 (Security in the Semi-Honest Model, based on [27]).

2.3. Kidney exchange terminology

Definition 2 (Compatibility Graph G C ).

Definition 3 (Exchange Cycle).

Definition 4 (Exchange Chain).

Definition 5 (Kidney Exchange Problem (with Exchange Chains)).

2.4. Integer programming for kidney exchange

Definition 6 (Cycle Formulation).

2 This is only more efficient in the privacy-preserving case as only there the complete graph G K has to be considered.

3.1. Basic operations

3 We use this implementation as it is part of MP-SPDZ [28], which we use for the implementation of our protocols. We note that there are more efficient shuffling gates for three computing peers that require O ( | V | 2 · s ) communication and O ( 1 ) rounds [5].

Functionality 1 ( G COMP - CHECK – Compatibility Check for Kidney Exchange, based on [17]).

Functionality 2 ( G IP - SETUP – Privacy-Preserving IP Setup for the Subset Formulation).

4.1. Prioritization criteria

Functionality 3 ( G PRIO – Privacy-Preserving Prioritization for the KEP).

5. Privacy-preserving protocols for solving the kidney exchange problem

5.1. Protocol π KEP - RND

5.1.1. Approach and ideal functionality

Definition 11 ( G EC : Exchange Constellation Graph [17]).

Definition 12 (Neighborhood Constellation [17]).

Functionality 4 ( F KEP - RND – Solving the KEP with Random Selection, based on [17]).

5.1.2. Protocol specification

5.1.4. Extension for exchange chains

5.2.1. Approach and ideal functionality

5.2.2. Protocol specification

5.2.4. Extension for exchange chains

5.3. Protocol π KEP - DP

5.3.1. Approach and ideal functionality

5.3.2. Protocol specification

5.3.4. Extension for exchange chains

6. Evaluation

4 https://github.com/data61/MP-SPDZ/releases/tag/v0.3.5

6.5. Discussion

7. Related work

7.1. Conventional kidney exchange

6 Note that the SMPC protocol from [16] already provides an efficient privacy-preserving solution for the special case of exchange cycles of size 2.

8. Conclusion and future work

Source code

Footnotes

Acknowledgments

Additional evaluation results

Protocols for exchange chains

Simulators

References

¹
Note that it is hard to develop an efficient data oblivious SMPC protocol for the KEP since the KEP is NP-complete for cycle size restrictions larger than 2 [1].

Definition 2 (Compatibility Graph $G^{C}$ ).

²
This is only more efficient in the privacy-preserving case as only there the complete graph $G_{K}$ has to be considered.

³
We use this implementation as it is part of MP-SPDZ [28], which we use for the implementation of our protocols. We note that there are more efficient shuffling gates for three computing peers that require $O (| V |^{2} \cdot s)$ communication and $O (1)$ rounds [5].

Functionality 1 ( $G_{COMP - CHECK}$ – Compatibility Check for Kidney Exchange, based on [17]).

Functionality 2 ( $G_{IP - SETUP}$ – Privacy-Preserving IP Setup for the Subset Formulation).

Functionality 3 ( $G_{PRIO}$ – Privacy-Preserving Prioritization for the KEP).

5.1. Protocol $π_{KEP - RND}$

Definition 11 ( $G^{EC}$ : Exchange Constellation Graph [17]).

Functionality 4 ( $F_{KEP - RND}$ – Solving the KEP with Random Selection, based on [17]).

5.3. Protocol $π_{KEP - DP}$

⁴
https://github.com/data61/MP-SPDZ/releases/tag/v0.3.5

⁶
Note that the SMPC protocol from [16] already provides an efficient privacy-preserving solution for the special case of exchange cycles of size 2.