Paper 2016/017

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

Helger Lipmaa, Payman Mohassel, and Saeed Sadeghian


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).

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
universal circuitsimplementationPrivate Function Evaluation
Contact author(s)
sadeghian @ gmail com
2016-01-08: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.