Marian Dietz
ETH Zurich

Hanjun Li
University of Washington

Huijia Lin
University of Washington

Keywords:

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.