Valiant's Universal Circuit is Practical

18.08.2016, 16:30 – 17:30

2016/08/18 16:30-17:30

Speaker: Ágnes Kiss| Location: Mornewegstraße 32 (S4|14), Room 3.1.01, Darmstadt

Organizer: CROSSING

Abstract

Universal circuits (UCs) are Boolean circuits that can be programmed to evaluate any circuit up to a given size k. They provide elegant solutions in various application scenarios for hiding the computed functionality, e.g. for private function evaluation (PFE), program obfuscation and for improving the flexibility of attribute-based encryption (ABE) schemes. The optimal size of a universal circuit is proven to be Ω(k log k). Valiant (STOC'76) proposed an asymptotically size-optimal UC construction, which has not been put in practice ever since. The only implementation of universal circuits was provided by Kolesnikov and Schneider (FC'08), with size O(k log^2 k).

In this talk, we provide an overview of Valiant's algorithm that highly relies on the notion of (edge-)universal graphs. We detail how universal graphs as well as universal circuits can be constructed using Valiant's algorithm. We discuss the programming of the circuit, elaborate on the size of both constructions and validate the practicality of Valiant's UC by giving details of our implementation of these size-optimized UCs and its example application of private function evaluation

Short Bio

Ágnes Kiss finished her M.Sc. studies in January 2015 in a double-degree program of the EIT Digital Master School (at University of Trento and TU Berlin). Since then, she is a PhD student at TU Darmstadt in the Engineering Cryptographic Protocols (Encrypto) Group supervised by Dr. Thomas Schneider. Her research focuses on efficient secure function evaluation protocols, both generic as well as task-specific algorithms.