Welcome to the resource topic for 2024/415
Title:
Column-wise Garbling, and How to Go Beyond the Linear Model
Authors: Lei Fan, Zhenghao Lu, Hong-Sheng Zhou
Abstract:In the linear garbling model introduced by Zahur, Rosulek, and Evans (Eurocrypt 2015), garbling an AND gate requires at least (2\kappa) bits of ciphertext, where \kappa is the security parameter. Though subsequent works, including those by Rosulek and Roy (Crypto 2021) and Acharya et al. (ACNS 2023), have advanced beyond these linear constraints, a more comprehensive design framework is yet to be developed.
Our work offers a novel, unified, and arguably simple perspective on garbled circuits. We introduce a hierarchy of models that captures all existing practical garbling schemes. By determining the lower bounds for these models, we elucidate the capabilities and limits of each. Notably, our findings suggest that simply integrating a nonlinear processing function or probabilistic considerations does not break the (2\kappa) lower bound by Zahur, Rosulek, and Evans. However, by incorporating column correlations, the bound can be reduced to ((1+1/w)\kappa), where (w\ge 1). Additionally, we demonstrate that a straightforward extension of Rosulek and Roy’s technique (Crypto 2021) does not yield improved results. We also present a methodology for crafting new models and for exploring further extensions of both the new and the existing models.
Our new models set the course for future designs. We introduce three innovative garbling schemes based on a common principle called ``majority voting.‘’ The third construction performs on par with the state-of-the-art.
ePrint: https://eprint.iacr.org/2024/415
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 .