Paper 2024/389

On the Feasibility of Sliced Garbling

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.

Note: A bug in Theorem 1 was brought to our attention by Lei Fan, Zenghao Lu, and Hong-Sheng Zhou \cite{cryptoeprint:2024/415}and Taechan Kim \cite{AC:Kim24}. The attack on the scheme that reveals the permute bits when garbled using the scheme shown in Figure 1. In particular, we have observed that there are linear dependencies in the system of equations corresponding to the scheme that can be exploited. With existing lower bounds following this work, we believe resolving this would be hard to achieve. The sections containing the separation result is not affected by this bug. A previous version of this paper included a result on "Oblivious Garbling" and it has now been separated from this paper and published in SCN'26 \cite{cryptoeprint:2026/1132}.