Welcome to the resource topic for 2024/389
Title:
On the Feasibility of Sliced Garbling
Authors: Tomer Ashur, Carmit Hazay, Rahul Satish
Abstract:Garbling schemes are one of the most fundamental objects in cryptography and have been studied extensively due to their broad applicability. The state-of-the-art is a construction in which XOR gates are free and AND gates require 3\kappa/2+\mathcal{O}(1) bits per gate, due to Rosulek and Roy (CRYPTO’21). An important technique in their garbling is slicing, which partitions the labels into two equal-length slices. In this paper, we explore the feasibility of the slicing technique for garbling schemes beyond the results introduced by Rosulek and Roy, demonstrating both its potential and its limitations.
In particular, we extend this technique to demonstrate the garbling of certain higher fan-in gadgets, and then use this to show that it is possible to garble 2-input AND gates at a cost of 4\kappa/3 +\mathcal{O}(1) bits. We then give a separation result showing that sliced garbling cannot be used to garble higher fan-in gadgets of degree \geq 3 when restricted to making queries that are linear functions of the input labels to the random oracle. We further demonstrate the usefulness of our techniques in the context of oblivious garbling, a newly introduced concept for capturing circuit hiding from the garbler. The complexity of our construction is superior to that of universal circuits, and grows linearly with circuit size.
ePrint: https://eprint.iacr.org/2024/389
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 .