International Association
for Cryptologic Research

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.

Authenticated PIR enables a server to initially commit to a database of $N$ items, for which a client can later privately obtain individual items with complexity sublinear in $N$, with the added guarantee that the retrieved item is consistent with the committed database. A crucial requirement is {\em privacy with abort}, i.e., the server should not learn anything about a query {\em even} if it learns whether the client aborts. This problem was recently considered by Colombo et al. (USENIX '23), who proposed solutions secure under the assumption that the database is committed to {\em honestly}. Here, we close this gap for their DDH-based scheme, and present a solution that tolerates fully malicious servers that provide potentially malformed commitments. Our scheme has communication and client computational complexity $\mathcal{O}_{\lambda}(\sqrt{N})$, does not require any additional assumptions, and does not introduce heavy machinery (e.g., generic succinct proofs). We do so by introducing \emph{validation queries}, which, from the server's perspective, are computationally indistinguishable from regular PIR queries. Provided that the server succeeds in correctly answering $\kappa$ such validation queries, the client is convinced with probability $1-\frac{1}{2^\kappa}$ that the server is unable to break privacy with abort.