Welcome to the resource topic for 2024/804
Title:
Analysis on Sliced Garbling via Algebraic Approach
Authors: 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).
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.
ePrint: https://eprint.iacr.org/2024/804
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 .