Welcome to the resource topic for 2022/1652
Title:
Improved Universal Circuits using Lookup Tables
Authors: Yann Disser, Daniel Günther, Thomas Schneider, Maximilian Stillger, Arthur Wigandt, Hossein Yalame
Abstract:A Universal Circuit (UC) is a Boolean circuit of size \Theta(n \log n) that can simulate any Boolean function up to a certain size n. Valiant (STOC’76) provided the first two UC constructions of asymptotic sizes \sim5 n\log n and \sim4.75 n\log n, and today’s most efficient construction of Liu et al. (CRYPTO’21) has size \sim3n\log n.
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.
Most existing UC constructions simulate circuits consisting of 2-input gates.
In this work, we study UCs that simulate circuits consisting of (\rho \rightarrow \omega)-Lookup Tables (LUTs) that map \rho inputs to \omega outputs.
Existing UC constructions can be easily extend to (\rho \rightarrow 1)-LUTs (we call this the fixed UC construction).
We further extend this to (\rho \rightarrow \omega)-LUTs.
Unfortunately, the size of the fixed UC construction is linear in the largest input size \rho of the LUT, i.e., even if only a single LUT in the circuit has a large input size, the size of the whole UC is dominated by this LUT size.
To circumvent this, we design a \emph{dynamic} UC construction, where the dimensions of the individual LUTs are public.
We implement the fixed and dynamic UC constructions based on the UC construction by Liu et al., which also is the first implementation of their construction. We show that the concrete size of our dynamic UC construction improves by at least 2\times over Liu et al.'s UC for all benchmark circuits, that are representative for many PFE applications.
ePrint: https://eprint.iacr.org/2022/1652
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .