Welcome to the resource topic for 2019/348
Title:
Efficient and Scalable Universal Circuits
Authors: Masaud Y. Alhassan, Daniel Günther, Ágnes Kiss, Thomas Schneider
Abstract:A universal circuit (UC) can be programmed to simulate any circuit up to a given size n by specifying its program inputs. It provides elegant solutions in various application scenarios, e.g., for private function evaluation (PFE) and for improving the flexibility of attribute-based encryption schemes. The asymptotic lower bound for the size of a UC is \Omega(n \log n) and Valiant (STOC’76) provided two theoretical constructions, the so-called 2-way and 4-way UCs (i.e., recursive constructions with 2 and 4 substructures), with asymptotic sizes 5n \log_2n and 4.75n \log_2n, respectively. In this article, we present and extend our results published in (Kiss and Schneider, EUROCRYPT’16) and (Günther et al., ASIACRYPT’17). We validate the practicality of Valiant’s UCs, by realizing the 2-way and 4-way UCs in our modular open-source implementations. We also provide an example implementation for PFE using these size-optimized UCs. We propose a 2/4-hybrid approach that combines the 2-way and the 4-way UCs in order to minimize the size of the resulting UC. We realize that the bottleneck in universal circuit generation and programming becomes the memory consumption of the program since the whole structure of size \mathcal{O}(n \log n) is handled by the algorithms in memory. In this work, we overcome this by designing novel scalable algorithms for the UC generation and programming. We show that the generation, which involves topological ordering of the UC as well, can be designed to be performed block by block from top to bottom, while the programming can be performed subcircuit by subcircuit. Both algorithms use only \mathcal{O}(n) memory at any point in time. We prove the practicality of our scalable design with a scalable proof-of-concept implementation for generating Valiant’s 4-way UC. We note that this can be extended to work with optimized building blocks analogously. Moreover, we substantially improve the size of our UCs by including and implementing the recent optimization of Zhao et al. (ePrint 2018/943) that reduces the asymptotic size of the 4-way UC to 4.5n\log_2n. Furthermore, we include their optimization in the implementation of our 2/4-hybrid UC which yields the smallest UC construction known so far.
ePrint: https://eprint.iacr.org/2019/348
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 .