back

Valiant’s Universal Circuit – Towards a Modular Construction and Implementation

Bachelor Thesis

Author

Daniel Günther

Motivation

A universal circuit (UC) can be programmed to simulate any circuit up to a given size n by specifying its program bits. UCs have several applications, including private function evaluation (PFE). The asymptotical lower bound for the size of a UC is proven to be Ω(nlogn). In fact, Valiant (STOC'76) provided two theoretical UC constructions using so-called 2-way and 4-way constructions. The 2-way UC has recently been brought into practice in concurrent and independent results by Kiss and Schneider (EUROCRYPT'16) and Lipmaa et al. (Eprint 2016/017). Moreover, the latter work generalized Valiant's construction to any k-way UC.

Goal

The goal of this thesis is to revisit Valiant's UC constructions and the recent results, and to provide a modular and generic embedding algorithm for any k-way UC. Furthermore, the possibility for a more efficient UC based on a 3-way recursive strategy as well as a hybrid approach that combines the 2-way with the 4-way UC in order to minimize the size of the resulting UC should be discussed.

Supervisors

Publications

Awards

1st Prize CAST IT-Security Award 2018 Category Bachelor Thesis