Private Function Evaluation for n-input Gates

Bachelor Thesis, Master Thesis

Motivation

The cryptographic primitive Private Function Evaluation (PFE) allows two parties to securely compute f(x), where x is the private input of one party and f is a private function given by the other party without learning anything but the output. There are many applications for PFE like insurance rate calculation [1], credit checking [2], and software diagnosis [3]. It was recently shown that, for large function sizes, homomorphic encryption (HE)-based PFE [4] outperforms the more general approaches that use a universal circuit (UC) [5] as public function in a multi-party computation (MPC) protocol. However, UC-based PFE protocols are way more flexible as they are fully compatible to well-studied generic MPC protocols and can implement Boolean circuits consisting of any gates, while HE-based PFE cannot be easily implemented in existing MPC tools and is restricted to circuits of two input NAND gates. This thesis should investigate how the size of UCs can be reduced by replacing function blocks that implement, e.g., lookup tables or complex functionalities, with n-input gates [6], which can be easily included into universal circuits and evaluated with corresponding generic MPC protocols.

Goal

The goal of this thesis is to implement n-input gate support into the UC implementation of Alhassan et al. [6]. This implementation then shall be used to compare the sizes of circuits optimized with n-input gates to equivalent circuits consisting of only 2-input gates. Finally, the optimized UCs have to be benchmarked with an MPC protocol and compared to previous works.

Requirements

  • Good programming skills in C++
  • At least basic knowledge of cryptography
  • High motivation to learn and ability to work independently
  • Knowledge of the English language, Git, and LaTeX

References

Supervisor