back

LORELEI: Locally Rewriting Logic with Ensemble Improvements

Master Thesis

Motivation

Many highly-efficient, but generic MPC protocols reside in specific domains such as arithmetic secret sharing, binary secret sharing, or garbled circuits. Mixing domains and protocols, trying to use the optimal primitives from different domains for each building block of a function, was shown to substantially improve the performance of MPC [1] with many state-of-the-art protocols adapting such techniques. But even without completely switching domains, protocols such as [2,3] internally utilize some intermediate domain during multiplications/ANDs which was later shown useful to compute some functions, e.g., dot products, even more efficiently. The more recent protocols ABY2.0 [4] and ASTRA [5] do not only inherit this behaviour, but can also combine it with multi fan-in multiplications to, e.g., compute lookup tables more efficiently [6]. Yet, in contrast to well-researched domain switching as in [1], the intermediate domain is only used inside low-level building blocks for special functions instead of using its more general power.

Goal

The goal of this thesis is trying to utilize the aforementioned power to a larger extent. First, the priorly implicitly handled intermediate domain has to be made explicit, considering it already for a function/circuit definition. Then, similar to prior protocol mixing works such as Silph [7], it becomes crucial to develop automated tools to optimize protocol performance by function/circuit restructuring to better utilize the newly gained freedom. Concretely, the protocols ABY2.0 [4] and ASTRA [5] shall be considered and extended, followed by an analysis of how well the novel techniques are able to improve their performance, compared to the original as well as improvements such as [6] that should be superseded by the new approach.

Requirements

  • Experience in working with MPC
  • Experience in term rewriting and discrete optimization
  • Good programming skills in C++ or Rust
  • High motivation & ability to work independently
  • Knowledge of the English language, Git, LaTeX, etc.

References

Supervisors