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.
References
[1]
D.J. Abraham, A. Blum and T. Sandholm, Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchange, ACM Conference on Electronic Commerce (2007), ACM.
[2]
R. Anderson, I. Ashlagi, D. 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).
[3]
T. Andersson, P. Biró, M. Calderön, P. Chromy, A.N. Costa, E. Cozzi, P. Delgado, P. Dworczak, P. Fiaschetti, M. Garcia, B. Haase-Kromwijk, A. Hemke, X. Klimentova, D. Kuypers, L. Lombardini, D. Manlove, W. Petterson, A. Rais, N. Santos, B. Smeulders, V. Sparacino, F. Spieksma, M. Valentín, J. van de Klundert, F. Vespasiano and A. Viana, Modelling and optimisation in European kidney exchange programmes, 2019, https://www.enckep-cost.eu/assets/content/156/enckep_wg1_handbook2-20210407142449-156.pdf.
[4]
T. Araki, J. Furukawa, Y. Lindell, A. Nof and K. Ohara, High-throughput semi-honest secure three-party computation with an honest majority, in: Computer and Communications Security, ACM, 2016.
[5]
T. Araki, J. Furukawa, K. Ohara, B. Pinkas, H. Rosemarin and H. Tsuchida, Secure graph analysis at scale, in: Computer and Communications Security, ACM, 2021.
[6]
I. Ashlagi, A. Bingaman, M. Burq, V. Manshadi, D. Gamarnik, C. 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.
[7]
I. Ashlagi and A.E. Roth, Kidney exchange: an operations perspective, Technical Report, 9, 2021, INFORMS.
[8]
T. Birka, K. Hamacher, T. Kussel, H. Möllering and T. Schneider, SPIKE: Secure and private investigation of the kidney exchange problem, BMC Medical Informatics and Decision Making 22(253) (2022).
[9]
P. Biró, B. Haase-Kromwijk, T. Andersson, E.I. Ásgeirsson, T. Baltesová, I. Boletis, C. Bolotinha, G. Bond, G. Böhmig, L. Burnapp et al., Building kidney exchange programmes in Europe – An overview of exchange practice and activities, Transplantation 103(7) (2019).
[10]
P. Biró, J. van de Klundert, D. Manlove, W. Pettersson, T. Andersson, L. Burnapp, P. Chromy, P. Delgado, P. Dworczak, B. Haase et al., Modelling and optimisation in European kidney exchange programmes, in: European Journal of Operational Research, Elsevier, 2019.
[11]
D. Bogdanov, M. Jõemets, S. Siim and M. 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]
D. Bogdanov, S. Laur and J. Willemson, Sharemind: A framework for fast privacy-preserving computations, in: European Symposium on Research in Computer Security, Springer, 2008.
[13]
P. Bogetoft, D.L. Christensen, I. Damgård, M. Geisler, T. Jakobsen, M. Krøigaard, J.D. Nielsen, J.B. Nielsen, K. Nielsen, J. Pagter et al., Secure multiparty computation goes live, in: International Conference on Financial Cryptography and Data Security, Springer, 2009.
[14]
M. Breuer, P. Hein, L. Pompe, B. Temme, U. Meyer and S. Wetzel, Solving the kidney exchange problem using privacy-preserving integer programming, in: Annual International Conference on Privacy, Security & Trust (PST), IEEE, 2022.
[15]
M. Breuer, P. Hein, L. Pompe, B. Temme, U. Meyer and S. 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:.
[16]
M. Breuer, U. Meyer and S. 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]
M. Breuer, U. Meyer, S. Wetzel and A. Mühlfeld, A privacy-preserving protocol for the kidney exchange problem, in: Workshop on Privacy in the Electronic Society, ACM, 2020.
[18]
R. Canetti, Security and composition of multiparty cryptographic protocols, Journal of CRYPTOLOGY 13 (2000), 143–202.
[19]
O. Catrina and S. De Hoogh, Improved primitives for secure multiparty integer computation, in: International Conference on Security and Cryptography for Networks, Springer, 2010.
[20]
O. Catrina and S.d. Hoogh, Secure multiparty linear programming using fixed-point arithmetic, in: European Symposium on Research in Computer Security, Springer, 2010.
[21]
I. Damgård and J.B. Nielsen, Universally composable efficient multiparty computation from threshold homomorphic encryption, in: Annual International Cryptology Conference, Springer, 2003.
[22]
G. Dantzig, Linear Programming and Extensions, Princeton University Press, 1963.
[23]
J.P. Dickerson, A.D. Procaccia and T. 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]
J. 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]
O. Goldreich, Foundations of Cryptography: Volume 2 – Basic Applications, Cambridge University Press, 2004.
[28]
M. 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]
J. Launchbury, I.S. Diatchki, T. DuBuisson and A. Adams-Moran, Efficient lookup-table protocol in secure multiparty computation, in: SIGPLAN International Conference on Functional Programming, ACM, 2012.
[31]
D.F. Manlove and G. 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.
[33]
A.J. Miller, B.A. Kiberd, I.P. Alwayn, A. 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.
[34]
Organ Procurement and Transplantation Network, https://optn.transplant.hrsa.gov/media/eavh5bf3/optn_policies.pdf, Accessed 16-Nov-2022.
[35]
A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, 1998.
[36]
A. Shamir, How to share a secret, Communications of the ACM 22(11) (1979).
[37]
T. Toft, Solving linear programs using multiparty computation, in: Financial Cryptography and Data Security, Springer, 2009.
[38]
A. Waksman, A permutation network, in: Journal of the ACM, Vol. 15, ACM, 1968.
[39]
H. 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]
S. Wüller, U. Meyer and S. Wetzel, Towards privacy-preserving multi-party bartering, in: Financial Cryptography and Data Security, Springer, 2017.
[41]
S. Zahur, X. Wang, M. Raykova, A. Gascón, J. Doerner, D. Evans and J. Katz, Revisiting square-root ORAM: Efficient random access in multi-party computation, in: IEEE Symposium on Security and Privacy, IEEE, 2016.
Index Terms
- Prioritization and exchange chains in privacy-preserving kidney exchange
Index terms have been assigned to the content through auto-classification.
Recommendations
A Privacy-Preserving Protocol for the Kidney Exchange Problem
WPES'20: Proceedings of the 19th Workshop on Privacy in the Electronic SocietyKidney donations from living donors form an attractive alternative to long waiting times on a list for a post-mortem donation. However, even if a living donor for a given patient is found, the donor's kidney might not meet the patient's medical ...
Efficient Privacy-Preserving Approximation of the Kidney Exchange Problem
ASIA CCS '24: Proceedings of the 19th ACM Asia Conference on Computer and Communications SecurityThe kidney exchange problem (KEP) seeks to find possible exchanges among pairs of patients and their incompatible kidney donors while meeting specific optimization criteria such as maximizing the overall number of possible transplants. Recently, several ...
Privacy-Preserving Maximum Matching on General Graphs and its Application to Enable Privacy-Preserving Kidney Exchange
CODASPY '22: Proceedings of the Twelfth ACM Conference on Data and Application Security and PrivacyTo this day, there are still some countries where the exchange of kidneys between multiple incompatible patient-donor pairs is restricted by law. Typically, legal regulations in this context are put in place to prohibit coercion and manipulation in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© 2024 – IOS Press. All rights reserved.
Publisher
IOS Press
Netherlands
Publication History
Published: 01 January 2024
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025