Paper 2024/2048

TinyLabels: How to Compress Garbled Circuit Input Labels, Efficiently

Abstract

Garbled circuits are a foundational primitive in both theory and practice of cryptography. Given $(\hat{C},K[x])$, where $\hat{C}$ is the garbling of a circuit C and $K[x]=\{K[i,x_i]\}$ are the input labels for an input $x$, anyone can recover $C(x)$, but nothing else about the input $x$. Most research efforts focus on minimizing the size of the garbled circuit $\hat{C}$. In contrast, the work by Applebaum, Ishai, Kushilevitz, and Waters (CRYPTO' 13) initiated the study of minimizing the cost for transferring the input labels $$. Later improved in a follow-up by Applebaum et al. (STOC' 23), the state-of-the-art techniques allow compressing the input labels to the optimal rate of $$. That is, each input label can be transferred by essentially sending 1 bit. However, existing solutions are computationally expensive, requiring large numbers of public-key operations (such as RSA exponentiation). In this work, we present an efficient input label compression technique based on Ring-LWE. We achieve the same optimal rate of $$, by making use of additional communication in an offline stage (before the input $$ becomes known), a paradigm that has already been explored in prior works. A novel feature of the offline communication in our scheme is that the information sent is either reusable or compressible using a random oracle, leading to small amortized offline cost $$. We further demonstrate concrete efficiency through an implementation whose online latency out-performs the naive baseline (which sends all of $$ in the online phase) in a realistic network with a bandwidth of up to 45Mbps. This break-even point could be pushed even further by leveraging the large potential for parallelization of computation. Finally, we apply our techniques to construct maliciously-secure two-party computation protocols with succinct online communication: The online phase starts once the circuit C becomes known, and requires exchanging only $$ bits (independent of $$). After inputs $$, $$ arrive, an additional $$ bits need to be sent.

Note: Dec. 24, 2024: added acknowledgements. Jan. 07, 2025: added reference to [GS18,GOS18] on pg. 3. Feb. 07, 2025: replaced wrong version of abstract on website. Mar. 12, 2025: updated title and added reference to implementation.