Cryptology ePrint Archive: Report 2016/017

Valiant's Universal Circuit: Improvements, Implementation, and Applications

Helger Lipmaa and Payman Mohassel and 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).

Category / Keywords: cryptographic protocols / universal circuits, implementation, Private Function Evaluation

Date: received 7 Jan 2016

Contact author: sadeghian at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160108:000306 (All versions of this report)

Short URL: ia.cr/2016/017

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]