back to list

Information Extraction Attacks on Private Kidney Exchange (and Beyond)

Bachelor Thesis

Motivation

Informally spoken, secure computation techniques allow processing of data “under encryption”. Protecting privacy is especially relevant in the health care domain, as nowadays more and more algorithmically driven diagnosis and treatment approaches are developed that analyze patients’ sensitive medical information.

Breuer et al. [1] propose a secure multi-party computation (MPC) protocol for the kidney exchange problem (KEP). When multiple patients in need for a kidney donation each only have an incompatible donor (e.g., a family member) available, the KEP identifies matches between those pairs such that each donor can donate to a compatible patient. The KEP itself is an optimization problem which is commonly tackled using integer linear programming (ILP).

The authors propose the first MPC protocol that solves the KEP using ILP while also preserving the patients’ and donors’ privacy. However, ILP is already expensive in the plaintext domain due to the KEP generally being NP-complete, while MPC also adds a significant overhead on top. Breuer et al. use a Branch-and-Bound approach based on ILP relaxation. To attain feasible protocol complexity, they leak intermediate information, namely, the structure of the search tree and number of iterations used to solve each ILP relaxation instance. The authors point out that those leakages are part of the protocols, but they do not formally analyze their effects on the patients’ and donors’ privacy guarantees. Instead, they claim those not to be harmful as they employ an additional shuffling to hide any relation between the search structure and individuals.

Goal

As the information leakage of the MPC protocol in [1] was not formally analyzed, we question the claim that it is not problematic. This thesis aims at concretely investigating and experimenting which effects the leakage of intermediate information in the protocol might have on privacy guarantees for patients and donors. For example, leakage thereby can be information about all involved patients/donors, a subset, or individuals. It can be identifying or excluding attribute values. In the thesis, the student may design edge cases that can lead to privacy violations. The overall goal is to derive a conclusion regarding the criticality of the information leakage that Breuer et al. claim to be acceptable.

Requirements

  • Solid understanding of Integer Linear Programming (ILP) and ILP solving (especially Branch-and-Bound) is beneficial
  • Interest in cryptography and secure computation
  • Programming experience (any language)
  • High motivation + ability to work independently
  • Knowledge of the English language, Git, LaTeX, etc. goes without saying

References

Supervisors