Valiant’s Universal Circuit – Towards a Modular Construction and Implementation
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.
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.
- Ágnes Kiss, M.Sc. (firstname.lastname@example.org-…)
- Prof. Dr.-Ing. Thomas Schneider (email@example.com-…)
- Daniel Günther, Ágnes Kiss, and Thomas Schneider: More Efficient Universal Circuit Constructions. In ASIACRYPT. Springer, 2017.
- Daniel Günther: Valiant's Universal Circuit – Towards a Modular Construction and Implementation. Bachelor Thesis, 2017.