More Efficient Universal Circuit Constructions
A universal circuit (UC) can be programmed to simulate any circuit up to a given size n by specifying its program bits. UCs have several applications, including private function evaluation (PFE). The asymptotical lower bound for the size of a UC is proven to be \(\varOmega (n\log n)\). In fact, Valiant (STOC’76) provided two theoretical UC constructions using so-called 2-way and 4-way constructions, with sizes\(~5n\log _2n\) and \(4.75n\log _2n\), respectively. The 2-way UC has recently been brought into practice in concurrent and independent results by Kiss and Schneider (EUROCRYPT’16) and Lipmaa et al. (Eprint 2016/017). Moreover, the latter work generalized Valiant’s construction to any k-way UC.