Memory-Efficient MPC for Large Circuits

Master Thesis

Motivation

The field of secure multi-party computation (MPC) has seen a rise in the number of published frameworks (see, e.g., ABY [1], MOTION [2], MP-SPDZ [3], and a comprehensive list of compilers in [4]). The purpose of the frameworks is to offer easy-to-use tools for software developers who are non-experts in MPC but want to apply the techniques in their applications, which usually also demand high efficiency. Previously, there have been many advances in developing novel MPC techniques which optimize runtime and communication, thus resulting in more scalable framework development. However, memory consumption is less frequently discussed even though it is an important factor especially for applications that run on smartphones, web browsers, or smart cards.

Goal

The goal of this thesis is to design and implement a memory efficient MPC framework by further developing our existing framework (written in Rust) for 2-party GMW. The design should include at minimum the concept of sub-circuits (see, e.g., [5]) that enables the developer to define smaller sub-functionalities, which are executed multiple times in the complete functionality without linearly increasing the memory consumption. Moreover, the phases of the underlying protocol must have a clear separation in the execution, meaning that the phases can be executed independently in different times (e.g., preprocessing overnight). The framework should provide full integration with standard operating systems and Android smartphones in order to enable benchmarking on multiple platforms. Finally, the framework must be compared extensively with the other existing state-of-the-art MPC frameworks in terms of memory consumption, as well as runtime and communication. Large scale experiments, similar to [6-7], should be performed successfully using the framework.

Requirements

  • Good programming skills in Rust
  • Basic knowledge of cryptography and secure multi-party computation
  • High motivation + ability to work independently
  • Knowledge of the English language, Git, LaTeX, etc. goes without saying

References

  • [1] Daniel Demmler, Thomas Schneider, and Michael Zohner. ABY – A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. In NDSS, 2015.
  • [2] Lennart Braun, Daniel Demmler, Thomas Schneider, and Oleksandr Tkachenko. MOTION – A Framework for Mixed-Protocol Multi-Party Computation. In TOPS, 2022.
  • [3] Marcel Keller. MP-SPDZ: A Versatile Framework for Multi-Party Computation. In CCS, 2020.
  • [4] Marcella Hastings, Brett Hemenway, Daniel Noble, and Steve Zdancewic. SoK: General-Purpose Compilers for Secure Multi-Party Computation. In S&P, 2019. https://github.com/MPC-SoK/frameworks
  • [5] Wilko Henecka and Thomas Schneider. Faster Secure Two-Party Computation with Less Memory. In AsiaCCS, 2013.
  • [6] Yan Huang, David Evans, Jonathan Katz, and Lior Malka. Faster Secure Two-Party Computation Using Garbled Circuits. In USENIX Security, 2011.
  • [7] Benjamin Kreuter, Abhi Shelat, and Chih-Hao Shen. Billion-Gate Secure Computation with Malicious Adversaries. In USENIX Security, 2012.

Supervisors