Garbled circuits are a foundational primitive in both theory and practice of cryptography. Given \((\widehat{C}, \textbf{K}[\textbf{x}])\) , where \(\widehat{C}\) is the garbling of a circuit C and \(\textbf{K}[\textbf{x}] = \{\textbf{K}[i, x_i]\}_{i \in [|\textbf{x}|]}\) are the input labels for an input \(\textbf{x}\) , anyone can recover \(C(\textbf{x})\) , but nothing else about input \(\textbf{x}\) . Most research efforts focus on minimizing the size of the garbled circuit \(\widehat{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 \(\textbf{K}[\textbf{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 \(\textbf{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(|\textbf{x}|)\) . We further demonstrate concrete efficiency through an implementation whose online latency outperforms the naive baseline (which sends all of \(\textbf{K}[\textbf{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 \(\textrm{poly}(\lambda )\) bits (independent of |C|). After inputs \(\textbf{x}_A, \textbf{x}_B\) arrive, an additional \(|\textbf{x}_A|+|\textbf{x}_B|+\textrm{poly}(\lambda )\) bits need to be sent.

TinyLabels: How to Compress Garbled Circuit Input Labels, Efficiently

会议论文
发表日期：

2025年

查看全文

Marian Dietz,
Hanjun Li,
Huijia Lin

摘要

Garbled circuits are a foundational primitive in both theory and practice of cryptography. Given \((\widehat{C}, \textbf{K}[\textbf{x}])\) , where \(\widehat{C}\) is the garbling of a circuit C and \(\textbf{K}[\textbf{x}] = \{\textbf{K}[i, x_i]\}_{i \in [|\textbf{x}|]}\) are the input labels for an input \(\textbf{x}\) , anyone can recover \(C(\textbf{x})\) , but nothing else about input \(\textbf{x}\) . Most research efforts focus on minimizing the size of the garbled circuit \(\widehat{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 \(\textbf{K}[\textbf{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 \(\textbf{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(|\textbf{x}|)\) . We further demonstrate concrete efficiency through an implementation whose online latency outperforms the naive baseline (which sends all of \(\textbf{K}[\textbf{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 \(\textrm{poly}(\lambda )\) bits (independent of |C|). After inputs \(\textbf{x}_A, \textbf{x}_B\) arrive, an additional \(|\textbf{x}_A|+|\textbf{x}_B|+\textrm{poly}(\lambda )\) bits need to be sent.