Paper 2022/1652

Breaking the Size Barrier: Universal Circuits meet Lookup Tables

Abstract

A Universal Circuit (UC) is a Boolean circuit of size $$ that can simulate any Boolean function up to a certain size $$. Valiant (STOC'76) provided the first two UC constructions of asymptotic sizes $$ and $$, and today's most efficient construction of Liu et al. (CRYPTO'21) has size $$. Evaluating a public UC with a secure Multi-Party Computation (MPC) protocol allows efficient Private Function Evaluation (PFE), where a private function is evaluated on private data. Previously, most UC constructions have only been developed for circuits consisting of 2-input gates. In this work, we generalize UCs to simulate circuits consisting of ($$)-Lookup Tables (LUTs) that map $$ input bits to $$ output bits. Our LUT-based UC (LUC) construction has an asymptotic size of $$ and improves the size of the UC over the best previous UC construction of Liu et al. (CRYPTO'21) by factors 1.12$$ - $$ for common functions. Our results show that the greatest size improvement is achieved for $$ inputs, and it decreases for $$. Furthermore, we introduce Varying Universal Circuits (VUCs), which reduce circuit size at the expense of leaking the number of inputs $$ and outputs $$ of each LUT. Our benchmarks demonstrate that VUCs can improve over the size of the LUC construction by a factor of up to $$.