LLVM-based Circuit Compilation for Pratical Secure Computation

LLVM-based Circuit Compilation for Pratical Secure Computation

Bachelor Thesis

Motivation

Evaluating functions securely on private inputs using existing two- or multi-party computation frameworks often requires implementing them as Boolean or arithmetic circuits. This is a tedious process when done by hand, requires extensive understanding of the underlying cryptographic protocols to achieve optimal results, and certainly is one of the reasons that prohibits the wide-ranging adaptation of secure computation in commercial applications.
Previous works have tried to address this issue by presenting approaches for automatic compilation of high-level code to circuit representations. Most notably, the HyCC compiler [1] studies compilation from ANSI C to optimized Boolean and arithmetic circuits while also selecting the most suitable cryptographic protocols for execution. However, works like HyCC allow compilation only from a very limited subset of a single language and more importantly neglect decades of research that went into optimizing conventional compilers.

Goal

The goal of this thesis is to enable automatic compilation of high-level code written in various programming languages to a circuit representation for practical secure computation using the LLVM compiler infrastructure. Concretely, a new LLVM back-end should be designed in order to synthesize (Boolean) circuits in a format similar to the widely-used Bristol format while benefiting from a range of existing LLVM front-ends and optimizations.
The proof-of-concept implementation must be able to automatically compile examples like “Yao’s millionaires problem” and biometric matching from high-level code written in various programming languages (at least C/C++, Rust, and Python). The quality of the generated circuits must be compared with existing manually created implementations and the results produced by HyCC [1] using suitable metrics. In an empirical performance evaluation, also the concrete computation and communication efficiency should be determined and compared by executing the circuits with a state-of-the-art multi-party computation framework in realistic network settings.
Advanced tasks include to extend LLVM for optimizing circuits with respect to the multiplicative depth and/or size, to also generate arithmetic in addition to Boolean circuits, and to study hybrid protocols via suitable decomposition, scheduling, and automatic protocol selection methods.

Requirements

  • Good programming skills in C/C++
  • At least basic knowledge of compiler infrastructures and cryptography
  • High motivation + ability to work independently
  • Knowledge of the English language, Git, LaTeX, etc. goes without saying

References

  • [1] Niklas Büscher, Daniel Demmler, Stefan Katzenbeisser, David Kretzmer, Thomas Schneider. HyCC: Compilation of Hybrid Protocols for Practical Secure Computation. In CCS'18.

Supervisor