Paper 2024/803

Can We Beat Three Halves Lower Bound?: (Im)Possibility of Reducing Communication Cost for Garbled Circuits

Chunghun Baek, Samsung Research
Taechan Kim, Samsung Research
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
Creative Commons Attribution-NonCommercial
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},
      note = {\url{https://eprint.iacr.org/2024/803}},
      url = {https://eprint.iacr.org/2024/803}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.