Welcome to the resource topic for 2016/093
Title:
Valiant’s Universal Circuit is Practical
Authors: Ágnes Kiss, Thomas Schneider
Abstract:Universal circuits (UCs) can be programmed to evaluate any circuit of a given size k. They provide elegant solutions in various application scenarios, e.g. for private function evaluation (PFE) and for improving the flexibility of attribute-based encryption (ABE) schemes. The optimal size of a universal circuit is proven to be \Omega(k\log k). Valiant (STOC’76) proposed a size-optimized 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 \mathcal{O}(k\log^2 k). In this paper, we refine the size of Valiant’s UC and further improve the construction by (at least) 2k. We show that due to recent optimizations and our improvements, it is the best solution to apply in the case for circuits with a constant number of inputs and outputs. When the number of inputs or outputs is linear in the number of gates, we propose a more efficient hybrid solution based on the two existing constructions. We validate the practicality of Valiant’s UC, by giving an example implementation for PFE using these size-optimized UCs.
ePrint: https://eprint.iacr.org/2016/093
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .