back

LLVM-based Circuit Compilation for Pratical Secure Computation

Bachelor Thesis

Published at 19. International Conference on Applied Cryptography and Network Security (ACNS'21)

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

Core data