CryptoDB
TinyLabels: How to Compress Garbled Circuit Input Labels, Efficiently
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| 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 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 K[x]. 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 1 + o(1). 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 1 + o(1), by making use of additional communication in an offline stage (before the input x 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 o(|x|). We further demonstrate concrete efficiency through an implementation whose online latency outperforms the naive baseline (which sends all of K[x] 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 poly(lambda) bits (independent of |C|). After inputs x_A, x_B arrive, an additional |x_A|+|x_B|+poly(lambda) bits need to be sent. |
BibTeX
@inproceedings{eurocrypt-2025-35128,
title={TinyLabels: How to Compress Garbled Circuit Input Labels, Efficiently},
publisher={Springer-Verlag},
author={Marian Dietz and Hanjun Li and Huijia Lin},
year=2025
}