back

Graph Reinforcement Learning for the MPC Protocol Mixing Problem

Master Thesis

Motivation

From enabling Danish farmers to participate in auctions without giving away their bids [1], to permitting the Estonian government to investigate systemic interdependencies while conforming to the law [2], multi party computation has enjoyed a fast-paced development in the last decades. Its core mechanism, the secure multiparty cryptographic protocol, allows parties to jointly compute a function without needing to trust each other [3]. As there exist different types of MPC protocols and each protocol has its own trade-offs, mixed-protocol MPC has been proposed, a concept where different protocols encrypt granular parts of an MPC program [4, 5]. Although mixed-protocol MPC drastically improves the computational efficiency of MPC [4, 5, 6], finding an optimal combination of more than two protocols is NP-hard [7]. To tackle this, hybrid MPCs compilers have been developed; however, they suffer from non-ideal cost models and simplifications in optimum search [6, 7, 8].

Goal

The goal of this thesis is to investigate protocol mixing can be formulated as a reinforcement learning problem [9, 10]. We explore a model-based, AlphaZero-like approach trained on runtimes, cost models from existing tools, and convex combinations of communication costs and runtimes on small graphs [6, 10, 11, 12, 13, 14]. We evaluate the resulting reinforcement learning approaches against modern MPC compilers using a unified MPC benchmark [6, 7].

Requirements

  • Programming skills in Python, C++ or Rust
  • At least basic knowledge of cryptography
  • Familiarity with machine learning and reinforcement learning in any common Python framework
  • High motivation + ability to work independently
  • Knowledge of the English language, Git, LaTeX, etc.

References

Supervisors

Core data