Paper 2018/943

Valiant's Universal Circuits Revisited: an Overall Improvement and a Lower Bound

Shuoyao Zhao, Yu Yu, Jiang Zhang, and Hanlin Liu

Abstract

A universal circuit (UC) is a general-purpose circuit that can simulate arbitrary circuits (up to a certain size $n$). At STOC 1976 Valiant presented a graph theoretic approach to the construction of UCs, where a UC is represented by an edge universal graph (EUG) and is recursively constructed using a dedicated graph object (referred to as supernode). As a main end result, Valiant constructed a 4-way supernode of size 19 and an EUG of size $4.75n\log n$ (omitting smaller terms), which remained the most size-efficient even to this day (after more than 4 decades). Motivated by the emerging applications of UCs in various privacy preserving computation scenarios, we revisit Valiant's universal circuits, and propose a size-optimal 4-way supernode of size 18, and an EUG of size $4.5n\log n$. As confirmed by our implementations, we reduce the size of universal circuits (and the number of AND gates) by more than 5\% in general (rather than just for small-size circuits in particular), and thus improve upon the efficiency of UC-based cryptographic applications accordingly. Our approach to the design of optimal supernodes is computer aided (rather than by hand as in previous works), which might be of independent interests. As a complement, we give lower bounds on the size of EUGs and UCs in Valiant's framework, which significantly improves upon the generic lower bound on UC size and therefore reduces the gap between theory and practice of universal circuits.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in ASIACRYPT 2019
Keywords
Universal CircuitsPrivate Function EvaluationMultiparty Computation
Contact author(s)
yuyuathk @ gmail com
History
2019-09-11: last of 5 revisions
2018-10-05: received
See all versions
Short URL
https://ia.cr/2018/943
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/943,
      author = {Shuoyao Zhao and Yu Yu and Jiang Zhang and Hanlin Liu},
      title = {Valiant's Universal Circuits Revisited: an Overall Improvement and a Lower Bound},
      howpublished = {Cryptology ePrint Archive, Paper 2018/943},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/943}},
      url = {https://eprint.iacr.org/2018/943}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.