back to list

A Systematic Comparison of HE-based Private Function Evaluation Protocols

Master Thesis

Motivation

Secure function evaluation (SFE) allows two parties to jointly compute a known function on their private data. Private function evaluation (PFE) extends this by allowing one of the parties to define a private function which can then be computed on the private data of the other party without any of the parties learning the other party's private input. Practical PFE has been implemented as SFE of so-called universal circuits (UCs) in [KS16,GKS17]. These circuits can be programmed to evaluate any functionality up to a given size by specifying a number of input bits to the UC.

In the last decade, other approaches were proposed for private function evaluation that do not depend on UCs. These protocols that are defined specifically for PFE are less generic but might achieve better performance in practice. Katz and Malka proposed a PFE scheme based on Yao's garbled circuit protocol in [KM11]. This protocol utilizes additively homomorphic encryption and achieves linear complexity in the circuit size. Mohassel and Sadeghian proposed a protocol with two instantiations in [MS13]. The first instantiation improves over the protocol by Katz and Malka, while the second protocol utilizes oblivious transfers (based on symmetric-key operations), and therefore can be more efficient in practice, despite its O(n log n) complexity in the size of the function n. This thesis will focus on comparing all approaches for practical PFE and implementing one or more of them (based on the thesis type). A comparison between these specific approaches and PFE with UCs is also to be performed.

Goal

The goal of this thesis is to show the practicality of the constructions presented in [KM11] and [MS13] by implementing one or more of the presented PFE protocols with state-of-the-art optimizations for the building blocks. Choosing the correct building blocks is crucial when practical implementations are concerned. The performance of these protocols is to be both theoretically and experimentally compared with the performance of PFE with universal circuits from [KS16, GKS17].

Tasks

The student will study the state-of-the-art PFE protocols presented in [KM11] and [MS13] and look into potential improvements based on the advances in the field of secure computation. Once the building blocks are identified, the student will implement one or more of the protocols and compare all existing approaches for practical PFE, both theoretically and experimentally.

Requirements

Applicants should have outstanding academic records, solid C/C++ programming skills, and be able to work independently.

References

  • [KM11]: Jonathan Katz and Lior Malka: Constant-Round Private Function Evaluation with Linear Complexity. In ASIACRYPT'11.
  • [MS13]: Payman Mohassel and Seyed Saeed Sadeghian: How to Hide Circuits in MPC an Efficient Framework for Private Function Evaluation. In EUROCRYPT'13.
  • [KS16]: Ágnes Kiss and Thomas Schneider: Valiant's Universal Circuit is Practical. In EUROCRYPT'16.
  • [GKS17]: Daniel Günther, Ágnes Kiss and Thomas Schneider: More Efficient Universal Circuit Constructions. In ASIACRYPT'17.

Start: 01.04.2018 or later

Supervisor

Publications