Paper 2022/1652

Improved Universal Circuits using Lookup Tables

Yann Disser, TU Darmstadt
Daniel Günther, TU Darmstadt
Thomas Schneider, TU Darmstadt
Maximilian Stillger, TU Darmstadt
Arthur Wigandt,, TU Darmstadt
Hossein Yalame, TU Darmstadt
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
No rights reserved
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.