CryptoDB
Pseudorandom Correlation Functions for Garbled Circuits
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| Abstract: | In this paper, we define the notion of pseudorandom correlation generators (PCGs) and functions (PCFs) for garbling correlations. With our Garbling PCG or PCF, two parties can non-interactively generate a virtually unbounded number of secret-shared garbled circuits and corresponding secret-shared garbled inputs. With the shares of the garbled circuit and garbled input, anyone can recover the garbled circuit and evaluate it to obtain the result of the computation in the clear. In the process of constructing Garbling PCFs, we introduce a new primitive that we call a Topology-Adaptive PCF (TAPCF), which we construct from two different variants of the learning parity with noise (LPN) assumption. Informally, a TAPCF is a PCF that additionally allows the target correlation to be specified on-demand (i.e., at evaluation time). Using our TAPCF construction as a building block, we construct a Garbling PCF that allows the parties to specify the circuit they wish to garble on-the-fly. Under realistic parameter settings, we estimate that, with our construction, two parties can generate one garbled circuit per second, for garbled circuits with 10,000 AND gates. We show that Garbling PCFs have several applications: We provide constructions for (1) an efficient homomorphic secret-sharing scheme for specific circuits, (2) a zero-knowledge proof system for homomorphic secret sharing that supports checking unstructured languages, and (3) a semi-honest reusable two-round, two-party computation protocol supporting non-interactive public outputs. |
BibTeX
@inproceedings{tcc-2025-36233,
title={Pseudorandom Correlation Functions for Garbled Circuits},
publisher={Springer-Verlag},
author={Geoffroy Couteau and Srinivas Devadas and Alexander Koch and Sacha Servan-Schreiber},
year=2025
}