Welcome to the resource topic for 2024/803
Title:
Can We Beat Three Halves Lower Bound?: (Im)Possibility of Reducing Communication Cost for Garbled Circuits
Authors: Chunghun Baek, Taechan Kim
Abstract:Recent improvements to garbled circuits are mainly focused on reducing their size.
The state-of-the-art construction of Rosulek and Roy (Crypto 2021) requires 1.5\kappa bits for garbling AND gates in the free-XOR setting.
This is below the previously proven lower bound 2\kappa in the linear garbling model of Zahur, Rosulek, and Evans (Eurocrypt 2015).
Whether their construction is optimal in a more inclusive model than the linear garbling model still remains open.
This paper begins by providing a comprehensive model for a large class of practical garbling schemes
and proves the lower bound for the size of the garbled AND gates in our model.
We show that garbled AND gates require at least 1.5\kappa bits in our new model with the free-XOR setting.
It is remarkable to see that the construction by Rosulek and Roy is already optimal
despite the fact that our model possibly captures any potential extension of their construction.
ePrint: https://eprint.iacr.org/2024/803
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 .