Paper 2024/803
Can We Beat Three Halves Lower Bound?: (Im)Possibility of Reducing Communication Cost for Garbled Circuits
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Garbled circuitLower boundsSecure computation
- Contact author(s)
-
ldfamily2000 @ gmail com
tckim1458 @ gmail com - History
- 2024-05-24: approved
- 2024-05-24: received
- See all versions
- Short URL
- https://ia.cr/2024/803
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2024/803,
author = {Chunghun Baek and Taechan Kim},
title = {Can We Beat Three Halves Lower Bound?: (Im)Possibility of Reducing Communication Cost for Garbled Circuits},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/803},
year = {2024},
url = {https://eprint.iacr.org/2024/803}
}