The Theory And Practice Of Universal Circuits And Applications To Cryptography

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 4decades).A universal circuits(UC)refers to a circuit that can be programmed to simulate any Boolean circuit C up to a given size.That is,a UC takes as input program bits p_C(that encodes C)in addition to an input x,and produces as output UC(x,p_C)=C(x).Motivated by the emerging applications of UCs in various privacy preserving computation scenarios,we revisit Valiant's universal circuits.To construct a universal circuit,Valiant modeled a circuit to a directed acyclic graph:each node in the graph denote a gate in the circuit and each edge denote a wire.Valiant also propose a new concept:Edge-Universal Graph(EUG).Loosely speaking,Universal Circuits to circuits is like Edge-Universal Graphs to Directed Acyclic Graphs.And the supernode is the kernel part of his construction,it is a building block which used to construct a EUG recursively.As one or our most important contricution,we propose a size-optimal 4-way supernode of size 18,and an EUG of size 4.5nlogn.As a practical consequence,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.