Pseudorandom Correlated Function for Rate-1 Garbling
The recent work of Liu, Wang, Yang, and Yu (EUROCRYPT 2025) introduced BitGC, a rate-1 garbling scheme for Boolean circuits where the size of the garbled circuit contains just 1 bit per gate. The scheme has modest evaluation costs (a constant number of homomorphic operations per gate) compared to other lattice-based succinct garbling schemes which rely on a non-black-box composition of fully homomorphic encryption and attribute-based encryption. Motivated by the goal of further compressing the garbled circuit while retaining the evaluation efficiency of BitGC, in this work, we introduce the notion of a pseudorandom correlation function (PCF) for garbling which effectively provides a compressed representation of the garbled circuit and its associated input labels. In a PCF for a garbling scheme, there are two correlated keys: a garbling key and an evaluation key. Using the garbling key, one can take any Boolean circuit and deterministically derive the associated garbled circuit. Conversely, using the evaluation key and the circuit , one can obtain the labels associated with the inputs to the circuit. Moreover, the size of the garbling key and the evaluation key depends only on the security parameter (independent of the size or depth of the circuit), and the same keys can be reused to derive garbled circuits and input encoding keys for any number of circuits. The main result in our work is a PCF for the BitGC garbling scheme from integer lattices.

