Paper 2022/1652

Breaking the Size Barrier: Universal Circuits meet 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

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. 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 ($\rho\rightarrow\omega$)-Lookup Tables (LUTs) that map $\rho$ input bits to $\omega$ output bits. Our LUT-based UC (LUC) construction has an asymptotic size of $1.5\rho\omega n \log \omega n$ and improves the size of the UC over the best previous UC construction of Liu et al. (CRYPTO'21) by factors 1.12$\times$ - $2.18\times$ for common functions. Our results show that the greatest size improvement is achieved for $\rho=3$ inputs, and it decreases for $\rho>3$. Furthermore, we introduce Varying Universal Circuits (VUCs), which reduce circuit size at the expense of leaking the number of inputs $\rho$ and outputs $\omega$ of each LUT. Our benchmarks demonstrate that VUCs can improve over the size of the LUC construction by a factor of up to $1.45\times$.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
universal circuitprivate function evaluationmulti-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
2023-09-22: last of 3 revisions
2022-11-28: received
See all versions
Short URL
No rights reserved


      author = {Yann Disser and Daniel Günther and Thomas Schneider and Maximilian Stillger and Arthur Wigandt, and Hossein Yalame},
      title = {Breaking the Size Barrier: Universal Circuits meet Lookup Tables},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1652},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.