How to Compress Garbled Circuit Input Labels, Efficiently
8Speakers: Hanjun Li, University of Washington
Garbled circuit is 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 have focused on minimizing the size of the garbling \hat{C}. In contrast, the work by Applebaum, Ishai, Kushilevitz, and Waters (CRYPTO' 13) initiated the study of minimizing the cost of 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 exponentiations). In this talk, we present an efficient input label compression technique based on Ring-LWE. It achieves the same optimal rate of 1 + o(1), by making use of additional communication in an offline stage (before the input x becomes known). The offline communication is either reusable or compressible using a random oracle, leading to a small amortized offline cost, o(|x|). We further demonstrate concrete efficiency through an implementation whose online latency out-performs 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 can be pushed further by leveraging the large potential for parallelization of computation. Finally, we present an application of our techniques: a maliciously-secure two-party computation protocol with succinct online communication. The online phase starts once the circuit C becomes known, and the parties exchange poly(\lambda) bits (independent of |C|). Then when inputs x_A, x_B become known, the parties exchange an additional |x_A| + |x_B | + poly(\lambda) bits.