[Resource Topic] 2024/527: Slice more? It leaks: Analysis on the paper ``On the Feasibility of Sliced Garbling''

Welcome to the resource topic for 2024/527

Slice more? It leaks: Analysis on the paper ``On the Feasibility of Sliced Garbling’’

Authors: Taechan Kim


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 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/527

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 .