Flexible File Format and Intermediate Representation for Secure Multi-Party Computation

Bachelor Thesis, Master Thesis

Motivation

Secure multi-party computation (MPC) allows distrusting parties to compute a public function of their private inputs without revealing any information beyond the output of the function. Decades after the introduction of MPC in 1980s, we now have not only theoretically interesting MPC protocols but also practically very efficient instantiations of those protocols that can be applied to relatively large real-world tasks and run in the order of only seconds or minutes. The tools for MPC are though still lagging behind and need improvement.

Although tools for efficient MPC exist, they are mostly fine-tuned for particular protocols or settings and allow only very specific formats, e.g., there are commonly used file formats such as the Bristol Fashion format [1], which is limited to Boolean circuits, or the HyCC format [2], which is undocumented. A major obstacle that prevents more flexibility in MPC tools is the lack of a file format for MPC that would not only be well-defined but also flexible and would support different representations, i.e., not only arithmetic and Boolean circuits but also custom building blocks, e.g., generic high-level non-cryptographic building blocks such as (secure) floating point operations that can then be replaced by an MPC framework with optimized circuits and additional cryptographic techniques such as oblivious transfer, commitments, and zero-knowledge proofs.

Goal

The main goal of this thesis is to design and fully define a new file format and in-memory intermediate representation for describing MPC functionalities that must be able to efficiently represent low-level circuits and conversions between these as well as high-level building blocks. While standardization of a set of operations is certainly necessary, the format also needs to allow custom extensions to enable protocol and implementation-specific optimizations applied by compilers. As cryptographic protocols and tooling are implemented in various programming languages, the format should be easily accessible without having to write custom parsers for each project.

As the first step, related work [3-9] should be reviewed for identifying trade-offs in other existing, more sophisticated MPC formats and languages. Further inspiration can be found in:

  • Hardware description languages such as VHDL or Verilog, which also combine low-level circuits and more complex predefined components.
  • The ONNX file format [10], which is a portable file format for neural networks that enables interoperability among a large selection of software and can be used as an intermediate representation (IR) between user-facing frontends and the execution backends. Furthermore, the ONNX C++ library provides infrastructure for optimization passes over the network description. Since it is based on Google Protocol Buffers [11], the network description is accessible from a variety of programming languages. A similar file format would surely be useful for the MPC domain.
  • CrypTFlow [12] includes a simple imperative language as low-level intermediate language (LLIL).
  • zkInterface tool and standard [13] for inter-operable implementation-independent zero-knowledge proofs.
  • The LLVM compiler [14] for programming language-independent code optimizations and compilation.

On the implementation side, the student will need to implement a parser for the designed MPC file format in the MOTION framework for MPC [15] in C++ and potentially in other one or two popular MPC frameworks. Also, a converter from circuit formats that are widely used in the MPC community, e.g., the Bristol [1] and HyCC [2] format, to the designed file format for MPC needs to be implemented.

Finally, the designed file format needs to be compared with related work [4-9], and the designed intermediate representation needs to be used to showcase how the performance of MPC protocols can be improved by iteratively running optimizations on the intermediate representation.

Requirements

  • Knowledge of secure computation is highly beneficial (e.g., via the “Cryptographic Protocols” course)
  • Knowledge in compiler design is beneficial
  • Basic knowledge of secure multi-party computation is beneficial
  • Good programming skills in C/C++ are beneficial
  • High motivation to learn and ability to work independently
  • Knowledge of the English language, Git, and LaTeX

References

Supervisors