CryptoDB
Breaking the Size Barrier: Universal Circuits meet Lookup Tables
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | ASIACRYPT 2023 |
| 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. 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$. |
BibTeX
@inproceedings{asiacrypt-2023-33481,
title={Breaking the Size Barrier: Universal Circuits meet Lookup Tables},
publisher={Springer-Verlag},
author={Yann Disser and Daniel Günther and Thomas Schneider and Maximilian Stillger and Arthur Wigandt and Hossein Yalame},
year=2023
}