[Resource Topic] 2024/804: Analysis on Sliced Garbling via Algebraic Approach

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 .