Welcome to the resource topic for 2024/1907
Title:
Towards Optimal Garbled Circuits in the Standard Model
Authors: Ruiyang Li, Chun Guo, Xiao Wang
Abstract:State-of-the-art garbling schemes for boolean circuits roughly consist of two families, i.e., ideal model garbling that combines linear operations and ideal blockciphers (aiming at maximizing performance), and PRF-based garbling that insists on using theoretically sound assumptions. In the linear garbling framework introduced by Zahur, Rosulek, and Evans (Eurocrypt 2015), it was established that garbling an AND gate requires at least 2(\kappa +1) bits of ciphertext, with \kappa as the security parameter. Recent contributions from Lei Fan et al. and Chunghun Baek et al. have provided a detailed model showing that, under the free-XOR setting, which relies on a non-standard assumption, garbling an AND gate requires at least 1.5\kappa + O(1) bits. In contrast, regarding PRF-based garbling, the general model and efficiency bounds remain open questions.
In this paper, we present a comprehensive model for PRF-based garbled circuits and establish both the communication and computation lower bound. Specifically, we demonstrate that garbling an AND gate requires at least 2\kappa + 2 bits communication and 6 PRF calls, while an XOR gate requires a minimum of \kappa bits communication and 4 PRF calls. Notably, the state-of-the-art garbling scheme (GLNP scheme) under the PRF assumption, introduced by Shay, Yehuda, Ariel, and Benny (JOC 2018), uses 2\kappa + 4 bits and 8 PRF calls for an AND gate, which exceeds our established lower bound. We finally introduce an optimal garbling scheme showing that our communication and computation lower bounds are tight.
ePrint: https://eprint.iacr.org/2024/1907
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .