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
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×.
Typ des Eintrags: | Konferenzveröffentlichung |
---|---|
Erschienen: | 2023 |
Autor(en): | Disser, Yann ; Günther, Daniel ; Schneider, Thomas ; Stillger, Maximilian ; Wigandt, Arthur ; Yalame, Hossein |
Art des Eintrags: | Bibliographie |
Titel: | Breaking the Size Barrier: Universal Circuits meet Lookup Tables |
Sprache: | Englisch |
Publikationsjahr: | 18 Dezember 2023 |
Verlag: | Springer |
Buchtitel: | Advances in Cryptology - ASIACRYPT 2023 |
Reihe: | Lecture Notes in Computer Science |
Band einer Reihe: | 14438 |
Veranstaltungstitel: | 29th International Conference on the Theory and Application of Cryptology and Information Security |
Veranstaltungsort: | Guangzhou, Peoples Republic China |
Veranstaltungsdatum: | 04.12.2023 - 08.12.2023 |
Auflage: | 1. Edt. |
DOI: | 10.1007/978-981-99-8721-4 |
Zugehörige Links: | |
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×. |
Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Praktische Kryptographie und Privatheit DFG-Sonderforschungsbereiche (inkl. Transregio) DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche DFG-Graduiertenkollegs DFG-Graduiertenkollegs > Graduiertenkolleg 2050 Privacy and Trust for Mobile Users DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1119: CROSSING – Kryptographiebasierte Sicherheitslösungen als Grundlage für Vertrauen in heutigen und zukünftigen IT-Systemen |
Hinterlegungsdatum: | 25 Jul 2024 07:47 |
Letzte Änderung: | 25 Jul 2024 07:47 |
PPN: | |
Export: | |
Suche nach Titel in: | TUfind oder in Google |
![]() |
Frage zum Eintrag |
Optionen (nur für Redakteure)
![]() |
Redaktionelle Details anzeigen |