Valiant's Universal Circuit - Towards a Modular Construction and Implementation

Bachelor Thesis



Secure Function Evaluation (SFE) allows two parties to evaluate a function without sharing their inputs with one another, while Private Function Evaluation (PFE) hides additionally the computed function which one party provides, i.e. PFE is SFE with private functions. PFE can be efficiently reduced to SFE by using a Universal Circuit (UC) as public function for the computation.
A UC is a special Boolean Circuit, which is able to simulate every function of a certain size n. The first implementation of a UC was provided by Kolesnikov and Schneider (FC’08). Valiant (STOC’76) proposed the first and more efficient UC construction of size O(n log n). He detailed two variants for his construction, one with 2-way and one with 4-way recursive structure. One of these two constructions - the 2-way split UC construction - was implemented by Kiss and Schneider (Eurocrypt’16). Lipmaa et al. (Eprint 2016/017) generalized this construction to a k-way split construction and concludes that the best performing construction would be the 4-way split construction. However, the 4-way split UC construction, achieving better concrete performance, was not implemented so far.
In this work, we design and implement a module for Valiant’s 4-way split UC construction. This module can be embedded into a toolchain for PFE, which was provided by Kiss and Schneider (Eurocrypt’16) - designed for their own UC implementation. Additionally, we propose a modular consideration of UCs using the k-way split construction by Lipmaa et al. (Eprint 2016/017).

Student: Daniel Günther

Publication: Daniel Günther - Valiant’s Universal Circuit - Towards a
Modular Construction and Implementation

Start: 01.10.2016

End: 30.03.2017


Research Areas: ENCRYPTO

A A A | Drucken Print | Impressum Impressum | Sitemap Sitemap | Suche Search | Kontakt Contact | Webseitenanalyse: Mehr Informationen
zum Seitenanfangzum Seitenanfang