Paper 2024/804

Analysis on Sliced Garbling via Algebraic Approach

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). Recently, Ashur, Hazay, and Satish~(eprint 2024/389) proposed a scheme that requires $4/3\kappa + O(1)$ bits for garbling AND gates. Precisely they extended the idea of \emph{slicing} introduced by Rosulek and Roy to garble 3-input gates of the form $g(u,v,w) := u(v+w)$. By setting $w = 0$, it can be used to garble AND gates with the improved communication costs. However, in this paper, we observe that the scheme proposed by Ashur, Hazy, and Satish leaks information on the permute bits, thereby allowing the evaluator to reveal information on the private inputs. To be precise, we show that in their garbling scheme, the evaluator can compute the bits $\alpha$ and $\beta + \gamma$, where $\alpha$, $\beta$, and $\gamma$ are the private permute bits of the input labels $A$, $B$, and $C$, respectively.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Garbled circuit
Contact author(s)
tckim1458 @ gmail com
History
2024-05-27: approved
2024-05-24: received
See all versions
Short URL
https://ia.cr/2024/804
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2024/804,
      author = {Taechan Kim},
      title = {Analysis on Sliced Garbling via Algebraic Approach},
      howpublished = {Cryptology ePrint Archive, Paper 2024/804},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/804}},
      url = {https://eprint.iacr.org/2024/804}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.