Disser, Yann ; Günther, Daniel ; Schneider, Thomas ; Stillger, Maximilian ; Wigandt, Arthur ; Yalame, Hossein (2023)
Breaking the Size Barrier: Universal Circuits meet Lookup Tables.
29th International Conference on the Theory and Application of Cryptology and Information Security. Guangzhou, Peoples Republic China (04.12.2023 - 08.12.2023)
doi: 10.1007/978-981-99-8721-4_1
Konferenzveröffentlichung, Bibliographie

Kurzbeschreibung (Abstract)

A Universal Circuit~(UC) is a Boolean circuit of size~Θ(n łog 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 ∼5 nłog n and ∼4.75 nłog n, and today's most efficient construction of Liu et al.~(CRYPTO'21) has size~∼3nłog 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 (ρ → ω)-Lookup Tables (LUTs) that map ρ input bits to ω output bits. Our LUT-based UC (LUC) construction has an asymptotic size of 1.5ρω n łog ω n and improves the size of the UC over the best previous UC construction of Liu et al. (CRYPTO'21) by factors 1.12× - 2.18× for common functions. Our results show that the greatest size improvement is achieved for ρ=3 inputs, and it decreases for ρ>3. Furthermore, we introduce Varying Universal Circuits (VUCs), which reduce circuit size at the expense of leaking the number of inputs ρ and outputs ω 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×.

Frage zum Eintrag

Redaktionelle Details anzeigen