Paper 2016/017

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

Helger Lipmaa, 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).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
universal circuitsimplementationPrivate Function Evaluation
Contact author(s)
sadeghian @ gmail com
History
2016-01-08: received
Short URL
https://ia.cr/2016/017
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/017,
      author = {Helger Lipmaa and Payman Mohassel and Saeed Sadeghian},
      title = {Valiant's Universal Circuit: Improvements, Implementation, and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2016/017},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/017}},
      url = {https://eprint.iacr.org/2016/017}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.