Welcome to the resource topic for 2016/017
Title:
Valiant’s Universal Circuit: Improvements, Implementation, and Applications
Authors: Helger Lipmaa, Payman Mohassel, Saeed Sadeghian
Abstract:A Universal Circuit (UC) is a circuit that can simulate any circuit of a maximum size, given its description as input. In this work, we look back at Valiant’s universal circuit construction from Valiant (STOC 1976). Although it yields asymptotically optimal UC, and has implications for important problems in cryptography such as ‘‘private function evaluation’’ (PFE) and ‘‘cryptographic program obfuscation’’, somewhat surprisingly, no implementations of the construction exist. We provide a more approachable description, improve its constant factors, and put forth the first complete implementation. We observe that our improved implementation of Valiant’s UC performs better than estimated and in fact, is almost always smaller than UC construction of Kolesnikov and Schneider (FC 2008). The UC circuits generated by our implementation can be used for benchmarking MPC protocols, and provide a point of comparison for any future PFE. We also observe, for the first time, that the same construction can be adapted to yield size optimized \emph{universal arithmetic circuit} (UAC).
ePrint: https://eprint.iacr.org/2016/017
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 .