Circuit constructions & optimizations

Circuits of interest to secure computation. Combinatorial aspects of circuits in general that affect their suitability for secure computation.

Category contains 2 papers:

[KS08b] Vladimir Kolesnikov, Thomas Schneider. A Practical Universal Circuit Construction and Secure Evaluation of Private Functions. FC 2008 [pdf] [bibtex]

Summary: Constructs a universal circuit that is asymptotically suboptimal (by a log factor) but whose concrete size is smaller than Valiant's (asymptotically optimal) construction for input circuits up to several thousand gates. »

[V76] Leslie Valiant. Universal Circuits. STOC 1976 [bibtex]

Summary: Construction of a "universal circuit" that takes an encoding of a circuit ⚠ {$C$} and value ⚠ {$x$} as input, and outputs ⚠ {$C(x)$} »