back

Accelerating Private Function Evaluation with a RAM Computation Model

Master Thesis

Motivation

A cryptographic protocol for Private Function Evaluation (PFE) allows two parties to securely compute some function f(x), where both x and f are private inputs given by the parties. Each party only learns the output of the function, but nothing about the other party's input. PFE can be derived from Secure Function Evaluation (SFE), where both parties input private data x1 and x2, respectively, computing a public function f(x1, x2). By using a Universal Circuit (UC) [6] as the public function f, the circuit can be programmed by private input to evaluate any function up to a certain size, yielding PFE.

In both SFE and PFE, most approaches require the function to be represented as a single circuit. Especially for programs with many conditionals, this representation incurs significant overhead since all possible branches must be represented in the circuit and hence get evaluated during protocol execution. A similar argument holds for dynamically sized loops, since they must be unrolled and the maximum number of iterations must be contained in the circuit.As an alternative to circuit-based computation, recent works use a sequential function representation similar to Assembly, to be computed by repeated evaluation of a CPU-like circuit, only evaluating a single program path. For example, TinyGarble [4] and GarbledCPU [7] use a full-fledged CPU evaluating RISC programs, also allowing PFE by providing the program instructions as private input. However, such approaches require heavy machinery for Oblivious Random-Access Machines (ORAM) and branching mechanisms (e.g., [2,3] in the Garbled Circuits (GC) [5] setting), incurring significant overhead for each single cycle. A recent work [1] evaluates multiple base instructions per cycle and therefore, improving the amortized overhead per instruction. However, this work requires the function to be public.

Goal

The goal of this thesis is to design and implement a PFE framework for sequential function representation. The design should consider state-of-the-art techniques from recent works in the RAM setting (e.g., [1,2,3]) in order to improve over previous frameworks. Modeling and analysis of the leakage of circuit information should be performed. The implementation is supposed to be built on top of pre-existing frameworks. Finally, the framework needs to be evaluated and compared with other pre-existing PFE implementations in terms of memory consumption, runtime, and communication

Requirements

  • Knowledge of C++ programming language
  • Basic understanding of RAM processors (e.g., by taking the course „Rechner Organisation“)
  • Knowledge of Secure Multiparty Computation
  • High motivation + ability to work independently
  • Knowledge of the English language, Git, LaTeX, etc.

References

Supervisors