TY - GEN
T1 - Valiant’s universal circuits revisited
T2 - 25th International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
AU - Zhao, Shuoyao
AU - Yu, Yu
AU - Zhang, Jiang
AU - Liu, Hanlin
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2019.
PY - 2019
Y1 - 2019
N2 - 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.75nlogn (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 4-way supernode of size 18, and an EUG of size 4.75nlogn. As confirmed by our implementations, we reduce the size of universal circuits (and the number of AND gates) by more than 5% in general, 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 interest. 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.
AB - 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.75nlogn (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 4-way supernode of size 18, and an EUG of size 4.75nlogn. As confirmed by our implementations, we reduce the size of universal circuits (and the number of AND gates) by more than 5% in general, 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 interest. 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.
UR - https://www.scopus.com/pages/publications/85076711141
U2 - 10.1007/978-3-030-34578-5_15
DO - 10.1007/978-3-030-34578-5_15
M3 - 会议稿件
AN - SCOPUS:85076711141
SN - 9783030345778
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 401
EP - 425
BT - Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, 2019, Proceedings
A2 - Galbraith, Steven D.
A2 - Moriai, Shiho
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 8 December 2019 through 12 December 2019
ER -