back

Framework for Scalable and Flexible Private Message-Passing-Style Graph Analysis

Bachelor Thesis

Motivation

With graphs being an excellent data representation for human interactions, graph algorithms are of high value for analysis of such, but may also run on sensitive information that should not be disclosed. MPC provides privacy-preserving protocols for such algorithms on some specific problems. To achieve better performance for a wider class of algorithms, the class of message-passing algorithms was found to be well usable in MPC, as shown in [1,2,3]. Any graph algorithm that can be formulated in a message-passing fashion where nodes pass data along edges and compute arbitrary, but local computation on it, can be computed using these works. Examples are algorithms for contact tracing, computing similarity measures, or computing independent sets.

Yet, usability is restricted by [1] being a decade old, [2] not providing any public implementation, and [3] further restricting the class of feasible algorithms while providing only incomplete benchmark-grade code. Considering more general MPC, MP-SPDZ [4] demonstrates that even sophisticated MPC protocols can be relatively easily utilized by practitioners by providing a simple, high-level API to the user as a level of abstraction. The generality of MP-SPDZ comes with drawbacks concerning, e.g., scalability, rendering it not being directly well suited for graph analysis. A similar, but less generic approach, tailored to the class of message-passing algorithms, offers the potential of a first-of-its-kind tool for usable and scalable graph analysis being available to a wide range of researchers.

Goal

The goal of this thesis is to design and implement a framework offering both usability similar to MP-SPDZ and scalability of message-passing graph analysis works in MPC. This requires the following steps:

  • A careful selection (and maybe combination) of protocol-level primitives provided by [1,2,3], suited for different possible requirements.
  • The design of an intuitive front-end to practitioners.
  • The implementation of a framework, implementing and linking together the chosen protocol-level primitives and the front-end with a strong focus on scalability to very large datasets (millions of nodes/edges).
  • Extensive benchmarking and comparison of the resulting framework.

Requirements

  • Good programming skills in C++ or Rust
  • Experience in software engineering
  • Interest in graph algorithms
  • High motivation to dive into recent research
  • Knowledge of the English language, Git, LaTeX, etc.

References

Supervisors