Paper 2022/1652
Improved Universal Circuits using Lookup Tables
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- universal circuit private function evaluation multi-party computation
- Contact author(s)
-
disser @ mathematik tu-darmstadt de
guenther @ encrypto cs tu-darmstadt de
schneider @ encrypto cs tu-darmstadt de
maximilian stillger @ arcor de
arthur wigandt @ protonmail com
yalame @ encrypto cs tu-darmstadt de - History
- 2022-11-28: revised
- 2022-11-28: received
- See all versions
- Short URL
- https://ia.cr/2022/1652
- License
-
CC0
BibTeX
@misc{cryptoeprint:2022/1652, author = {Yann Disser and Daniel Günther and Thomas Schneider and Maximilian Stillger and Arthur Wigandt, and Hossein Yalame}, title = {Improved Universal Circuits using Lookup Tables}, howpublished = {Cryptology ePrint Archive, Paper 2022/1652}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1652}}, url = {https://eprint.iacr.org/2022/1652} }