A Practical Universal Circuit Construction and Secure Evaluation of Private Functions

We consider general secure function evaluation (SFE) of {em private functions} (PF-SFE). Recall, privacy of functions is often most efficiently achieved by general SFE cite{Yao82Protocols,Yao86 How,LindellPi04} of a Universal Circuit (UC). Our main contribution is a new simple and efficient UC construction. Our circuit UCk, universal for circuits of $k$ gates, has size $sim 1.5 k log^2 k$ and depth $sim k log k$. It is up to $50%$ smaller than the best UC (of Valiant cite{Valiant76}, of size $sim 19klog k$) for circuits of size up to $approx 5000$ gates. Our improvement results in corresponding performance improvement of SFE of (small) private functions. Since, due to cost, only small circuits (i.e. $